[정렬] 백준 1181 :: 단어 정렬

단어 정렬 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	20685	7576	5424	37.225%

문제

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

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

입력

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

출력

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

예제 입력 1 

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

예제 출력 1 

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

 문제 풀이

1차 시도 ( 4492 KB, 32 ms)

std::string, std::vector 사용.

중복되는 요소는 std::unique 함수로 배제.

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

bool compare(const string &s1, const string &s2) {
        if (s1.size() == s2.size()) return s1 < s2;
        else return s1.size() < s2.size();   
}

int N;
char word[51];
vector<string> dict;

int main(void) {
        scanf("%d", &N); 
        for (int i = 0; i < N; i++) {
                scanf("%s", word);
                dict.push_back((string)word);
        }

        vector<string>::iterator iter;
        vector<string>::iterator end_iter;
        
        sort(dict.begin(), dict.end(), compare);
        end_iter = unique(dict.begin(), dict.end());

        for (iter = dict.begin(); iter != end_iter; iter++) {
                printf("%s\n", (*iter).c_str()); 
        }
        return 0;
}

2차 시도 ( 4916 KB, 12 ms)

저수준 데이터 입출력 사용

string 대신 char[50],  vector 대신 array.

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

// fast_io 라이브러리 생략.


struct word {
        char data[51];
};
bool compare(const word& s1, const word& s2){
        auto len_s1 = strlen(s1.data);
        auto len_s2 = strlen(s2.data);
        if(len_s1 != len_s2) return len_s1 < len_s2;
        return 0 > strcmp(s1.data, s2.data);
}
bool isEquals(const word &s1, const word &s2){
        for(auto i=0; i<=50; i++){
                if(s1.data[i] != s2.data[i]) return false;
                if(s1.data[i] == 0) return true;
        }
        return true;
}


int main() {
        int N;
        int_io(READ, N);
        word arr[N];
        memset(arr, 0, sizeof arr);

        for(int i=0; i<N; i++){
                word_io(READ, arr[i].data);
        }
        sort(arr, arr+N, compare);
        auto end = unique(arr, arr + N, isEquals) - arr;
        for(int i=0; i<end; i++){
                word_io(WRITE, arr[i].data);
                char_io(WRITE, '\n');
        }
        char_io(WRITE, EOF);
}