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

https://www.acmicpc.net/problem/1181

제출 코드

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

bool comp(string &a, string &b)
{
    if (a.length() == b.length())
        return a < b;
    else
        return a.length() < b.length();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    string w;
    set<string> words;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> w;
        words.insert(w);
    }

    vector<string> v(words.begin(), words.end());
    sort(v.begin(), v.end(), comp);

    for (auto res : v)
        cout << res << '\n';
}

set을 활용하면 자동으로 중복 없이 string을 저장할 수 있다

중복없이 저장된 set을 길이가 짧은 것부터 정렬시키기 위해 vector로 옮겨준다

 

sort 함수에서 compare으로 쓰인 comp에서는 1순위로 길이가 짧은 것부터, 길이가 같다면 사전순으로 앞선것부터 정렬되도록 작성해준다

 

정렬이 끝났으면 vector에 들어있는 string들을 순서대로 출력한다

+) set의 정렬 기준은 구조체 형태로 정의되어 있기 때문에 이 부분을 변경해 주면 정렬 자체를 문제에 기준에 맞게끔 할 수도 있다 (참고: https://chanhuiseok.github.io/posts/algo-46/)

 

풀이 후 추가적으로 찾아보니 vector에서 중복된 원소를 지울 수가 있었다

이 문제의 경우 굳이 몇 번 등장했는지 체크할 필요가 없었기 때문에 vector의 unique, erase를 사용해 봐도 좋을 것 같았다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool comp(string &a, string &b)
{
    if (a.length() == b.length())
        return a < b;
    else
        return a.length() < b.length();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    string w;
    vector<string> words;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> w;
        words.push_back(w);
    }

    sort(words.begin(), words.end(), comp);
    words.erase(unique(words.begin(), words.end()), words.end());

    for (auto res : words)
        cout << res << '\n';
}

작성한 코드는 위와 같다

vector에 입력된 단어들을 넣고, 중복단어가 있는 상태에서 정렬을 해 준다

그리고 중복된 단어들을 지운 후 출력한다

 

정렬하는 것은 위에서의 방법과 동일하고

unique(시작점, 끝지점) 함수를 이용하면 연속하여 중복된 요소들을 제거하고, 뒤에 나머지가 남아 있다

(뒤에 남는 게 정렬된 중복된 요소들은 아니고, 정렬을 마친 시점에 남아있는 값이다

참고: https://velog.io/@whipbaek/c-unique-%ED%95%A8%EC%88%98%EC%97%90-%EA%B4%80%ED%95%98%EC%97%AC)

 

그리고 unique 함수를 사용하면 중복된 요소들이 모인 부분의 시작점 값을 반환하는데, 이를 이용해서 중복 요소의 시작점부터 맨 끝까지 erase 함수로 지워줄 수 있다

속도면에서도 더 빠르고 더 간단하게 풀 수 있었다