# 백준 : 단어 정렬(1181)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1181_word%20sorting)

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

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

int main(void) {
    // insert code here...
    int count;
    string str;
    vector <string> arr;
    vector <string> temp_arr;
   
    cin>>count;
    for(int i=0; i<count; i++) {
        cin>>str;
        arr.push_back(str);
    }
   
    sort(arr.begin(), arr.end());
    temp_arr.push_back(arr[0]);
    for(int i=1; i<arr.size(); i++) {
        if(arr[i-1] != arr[i]) {
            temp_arr.push_back(arr[i]);
        }
    }
   
    sort(temp_arr.begin(), temp_arr.end(), compare);
    for(int i=0; i<temp_arr.size(); i++) {
        cout<<temp_arr[i]<<endl;
    }
    return 0;
}

풀이

정렬에서 조금 더 난이도(라고 하기엔 좀 그렇지만)가 있는 단어 정렬을 풀어보았다. 
주어진 조건은 두가지이다. 길이에 따라서 먼저 정렬을 하되, 길이가 같은 경우에는 알파벳이 더 빠른 순서대로 정렬할 것. 그렇다면 정렬을 두번 하되, 순서를 어떻게 할 것인가를 정해야 한다.
요점은 얼만큼 덜 움직이면서 빠르게 정렬을 할 것인가인데, 나는 알파벳 순서대로 먼저 정렬을 하고, 그 과정에서 중복되는 단어를 지운 다음에 다시 정렬하는 방법을 택했다.
(물론 한번에 저 두 과정을 수행할 수도 있지만, 아직 나는 내공이 부족한 관계로 두번에 나누어서 진행하였다)

이번 문제를 풀면서 새롭게 알게 된 것은 STL의 내장함수 'sort'가 생각외로 꽤 많은 역할을 감당할 수 있다는 것이다. 단순히 길이에 따른 정렬만이 아니라 문자열을 구성하는 알파벳 순서에 따라서도 정렬이 가능하다는 것을 볼 수 있었다. 즉, 우리는 이 엄청난 함수 때문에 일일이 비교하고 넣고 하는 과정자체를 코드로 구현할 필요가 없다는 것이다.

무튼 소스에서도 볼 수 있듯이 처음에 알파벳 순서대로 정렬을 한다. 그러면 자연스레 중복되는 녀석들이 연속해서 몰려있을 것이다. 그러면 이전 노드와 현재 노드를 비교해서 중복되지 않으면 새로운 벡터에 추가한다. (새롭게 만들어진 이 벡터를 가지고 다시 정렬을 진행한다)

새롭게 만들어진 녀석은 compare라는 새롭게 만들어진 함수를 이용하여 추가적인 비교를 진행한다. 사이즈가 다르면 우선 오름차순으로 정렬하고, 만약 사이즈가 동일한 경우에만 알파벳 순서에 따라 비교한다. sort 내장 함수를 그냥 사용하게되면 문자열의 경우 알파벳 순서에 따라 정렬하기 때문에 위와 같이 비교문을 작성하였다.