백준 1181번 단어 정렬[C++]

문제 해결 전략 :  문제에서 요구한대로 정렬 -> 중복 제거 -> 출력 순서대로만 하면 되는 문제이다. 다만, 나는 정렬과 중복 제거를 구체적으로 어떻게 하는지 몰라서 헤맸다. 이번 기회에 어떻게 하는지 구체적으로 배웠다.

 

문제 해결 소감 : 내가 배우지 않은 std::sort, std::unique를 사용하여 문제를 해결했다. 고마워 챗 gpt!!! 더 고민한다고 되는 일은 아니었기 때문에 인공지능한테 물어봐서 확실히 내 것으로 만들면 괜찮다고 생각한다. std::sort는 intro sort를 사용한다고 하는데 그게 뭔지 알아봐야 겠다.(힙과 퀵 정렬은 혼용사용한다고 한다는데 이것도 뭔지 몰라서;;) <alogrithm> 라이브러리는 처음 사용해 보는데 아직 배움이 부족한거 같다. 더 열심히 해야겠다.

 

<처음 코드>

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int N;
std::string word;
std::vector<std::string> vec;
int main(void)
{
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> word;
        vec.push_back(word);
    }

    for (int i = 0; i < N; ++i)
    {
        for (int k = 0; k < N; ++k)
        {
            std::string temp;
            if (vec[i].size() < vec[k].size() && i > k)
            {
                temp = vec[i];
                vec[i] = vec[k];
                vec[k] = temp;
            }
        }
    } // 문자수 적은게 앞으로 오게 정렬
    for (int i = 0; i < N; ++i)
    {
        for (int k = 0; k < N; ++k)
        {
            std::string temp;
            if (vec[i].size() == vec[k].size() && vec[i] < vec[k] && i > k)
            {
                temp = vec[i];
                vec[i] = vec[k];
                vec[k] = temp;
            }
        } // 길이가 같으면 사전순 정렬
    }
    auto last = std::unique(vec.begin(), vec.end());

    vec.erase(last, vec.end());

    for (auto c : vec)
    {
        std::cout << c << std::endl;
    }
    return 0;
}

채점결과 : 시간 초과

 시간 초과가 났다. 이중 반복문이 2개 들어있어서 시간 내에 프로그램이 돌아가지 않은 것 같다. 정답 유무는 알려주지 않아서 확실하게 알 수는 없지만 예시 입력을 넣었을 때 올바르게 작동했으므로 코드 자체는 맞았을 것 같다.

<수정 코드>

기존 문제 해결 방법 : O(n2)을 O(logn)으로 줄이기 위해서 std::sort를 사용했다. 또한, 비교함수라는 것을 이용해서 두가 지 문제 요구사항에 부합하게 정렬되도록 하였다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int N;
std::string word;
std::vector<std::string> vec;

bool compare(std::string &a, std::string &b)
{
    if (a.size() != b.size())
    {
        return a.size() < b.size();
    }
    return a < b;
}
int main(void)
{
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> word;
        vec.push_back(word);
    }
    std::sort(vec.begin(), vec.end(), compare);

    auto last = std::unique(vec.begin(), vec.end());

    vec.erase(last, vec.end());

    for (auto c : vec)
    {
        std::cout << c << std::endl;
    }
    return 0;
}