[BOJ1181][C++] 단어 정렬

문제

알파벳 소문자로 이루어진 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

 

 

출처

· 문제를 만든 사람: author5

 

 

알고리즘 분류

· 정렬

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
#define N 20001
 
bool Comp(string a, string b)
{
    if (a.length() != b.length()) {
        return a.length() < b.length();    // 오름차순 정렬                                                                    
    }
    else {
        return a < b;    // 사전 순 정렬  
    }
}
 
int main()
{
    string ip[N];
    int num;
    
    cin >> num;
    cin.ignore();
    for (int i = 0; i < num; i++) {
        getline(cin, ip[i]);
    }
    
    sort(ip, ip + num, Comp);
    for (int i = 0; i < num; i++) {
        if(ip[i] == ip[i-1]) {    // 중복 제거
            continue;
        }
        else {
            cout << ip[i] << endl;
        }
    }
    
    return 0;
}

---

sort() 함수의 정렬 기준을 이용하여 문제를 풀었다.

정렬 기준 함수에 return a < b;를 추가하여 문자의 길이가 같을 경우 사전 순으로 정렬할 수 있다는 점이 놀라웠다.

예)

string a = "ios";  string b = "iab";  cout << (a < b) << endl;     // 0  cout << (a > b) << endl;     // 1