[BOJ-1181] 단어 정렬

문제

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

 

알고리즘 분류

• 문자열
• 정렬

 

문제 출처

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

1181번: 단어 정렬

 

문제 해결 방법

• 다음과 같이 직접 만든 커스텀 함수를 sort() 의 콜백 함수로 사용하여 문제를 해결하였다.

bool Compare(string a, string b) {
    if (a.size() == b.size()) {    // 길이가 같으면
        return a < b;    // 사전 순으로
    }
    return a.size() < b.size();    // 길이가 짧은 것 부터
}

 

• 중복된 단어는 한 번만 출력되도록 해야 했는데, 여러 가지 방법을 생각해보다가 2중 for 문을 돌려서 벡터 내부에서 중복되는 요소를 공백(" ")으로 바꿔준 후, 나중에 출력할 때 공백이 아닌 문자만 출력하는 방식을 사용하였다.

 // 벡터 내의 중복된 단어 제거
for (int i = 0; i < words.size(); i++) {
    for (int j = i + 1; j < words.size(); j++) {
        if (words[i] == words[j]) {    // 중복되는 단어가 있는 경우
            words[j] = " ";    // 두 번째 중복된 단어를 공백(" ")으로 바꾼다.
        }
    }
}

for (auto i : words) {
    if (i != " ") {    // 공백이 아닌 문자만 출력
        cout << i << '\n';
    }
}

 

코드

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

int N;
string word;
vector<string> words;    

bool Compare(string a, string b) {
    if (a.size() == b.size()) {    // 길이가 같으면
        return a < b;    // 사전 순으로
    }
    return a.size() < b.size();    // 길이가 짧은 것 부터
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> word;
        words.push_back(word);
    }

    sort(words.begin(), words.end(), Compare);

    // 벡터 내의 중복된 단어 제거
    for (int i = 0; i < words.size(); i++) {
        for (int j = i + 1; j < words.size(); j++) {
            if (words[i] == words[j]) {    // 중복되는 단어가 있는 경우
                words[j] = " ";    // 두 번째 중복된 단어를 공백(" ")으로 바꾼다.
            }
        }
    }

    for (auto i : words) {
        if (i != " ") {    // 공백이 아닌 문자만 출력
            cout << i << '\n';
        }
    }

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정렬]
• 실버V