[C/C++] 단어 정렬 (백준 1181)

문제

 

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

 

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

입력

 

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

 

출력

 

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

풀이

 

일단 지금은 정렬을 공부하는 마음으로 문제들을 풀어나가고 있기 때문에 이것저것 아이디어를 짜보고 거기에 맞는 함수를 찾는 방식으로 문제를 풀고 있다.

 

1. 숫자를 비교

2. 사전순서로 비교

 

이렇게 2가지로 나눠서 풀이가 가능한데 여기서 이전 포스팅에 적었던 조건을 사용하면 쉽게 풀 수 있다.

 

그런데 문제가 생겼다.  그냥 정렬을 해버리니 정렬은 잘되었지만 중복이 사라지지가 않는다. 그래서 찾아봤더니 C++에 중복을 완전히 제거하는건 따로 없고 공정을 거쳐야한다고 한다.

 

코드

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool compare(string a, string b){
    if(a.size() == b.size()){
        return a < b;
    } else {
        return a.size() < b.size();
    }
}

int main(void){
    vector<string> word_v;

    int n;
    scanf("%d", &n);

    for(int i = 0 ; i < n ; i++){
        string temp;
        cin >> temp;
        word_v.push_back(temp);
    }

    sort(word_v.begin(),word_v.end(),compare);
    word_v.erase(unique(word_v.begin(),word_v.end()),word_v.end());

    for(auto const& word : word_v){
        cout << word << endl;
    }

    return 0;
}

 

일단 sort까지는 평범하다 sort에 사용한 compare함수를 보면 길이가 같다면 a < b (사전순)으로 정렬하고 그게 아니라면 크기 순으로 정렬한다... 고 보면 될 것 같다. 많이 사용해야지 몸에 익숙해지는 그런 함수이다.

 

문제는 sort 밑에 있는 중복 제거 코드인데

 

벡터.erase(unique((시작),(끝)), (끝)); 으로 이루어지는 중복제거 코드이다. uniique를 통해서 일단 중복되지 않는 원소들을 앞으로 중복되는 원소를 뒤로 보내는데 이때 보내는 원소들은 다 쓰레기 값으로 뒤로보내진다고 한다. 이 상태애서 erase를 통해서 {중복 아닌 원소들} | {중복 되었던 쓰레기 값들} 이 구조에서 중간의 | 에서 문장의 마지막까지 지우면 {중복 아닌 원소들}만 남게 되는 것이다.

 

써보니 복잡하긴한데 아무튼 중복을 확실하게 지워준다.

 

이번에는 벡터.erase(unique(벡터.begin(),벡터.end()), 벡터.end())를 숙지하고 가면 좋을 것 같다.