[백준] 20920번 : 영단어 암기는 괴로워 (C++) - 실버 3

이 문제는 백준 알고리즘에서 제공하는 단계별 문제 풀이 중 '심화' 단계에 해당하는 조건에 따른 정렬 문제이다.

 

링크 : https://www.acmicpc.net/problem/20920

[ 그림 1 ] 20920번 문제 전문

 

 

 

 

다음으로 코드 전문이다. 문제 해결을 위해 떠올렸어야 할 요소들을 각각의 코드와 비교하며 서술하고자 한다.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

void fast_io() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

bool compare(pair<string, int> &a, pair<string, int> &b) {
    if (a.second == b.second) {
        if (a.first.length() == b.first.length()) {
            return a.first < b.first;
        }
        return a.first.length() > b.first.length();
    }
    return a.second > b.second;
}

int N = 0, M = 0;
map<string, int> word_map;
    
int main() {
    fast_io();
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string word;
        cin >> word;
        if (word.length() >= M) {
            word_map[word]++;
        }
    }

    vector<pair<string, int> > word_vec(word_map.begin(), word_map.end());
    sort(word_vec.begin(), word_vec.end(), compare);

    for (auto it : word_vec) {
        cout << it.first << "\n";
    }
}

 

해당 문제는 논리 연산 처리 방식과 C++에서 제공해주는 표준 라이브러리인 Algorithm의 sort 함수의 활용 방식에 대한 고민해보기 좋은 문제였다.

 

먼저 논리 연산에 대해 생각해보자.

 

위의 문제에서 정렬을 위해 제시한 조건은 3개이다. 이 말은 즉 조건에 따른 경우의 수가 총 2^3인 8가지라는 점을 시사한다는 것이다. 만약 이를 우리가 기존에 알고 있는 조건문 작성 방식인 if와 else if, else로 작성하면 조건에 대한 서술이 길어질뿐 만 아니라 가독성이 떨어지는 문제가 발생한다. 

 

예를 들어 '현재 단어가 이전 단어보다 빈도가 적으면서, 현재 단어의 길이가 이전 단어 길이보다 짧고, 알파벳 사전 순으로 앞에 있을 경우'라면, 각 경우가 서로 연속하여 발생하므로 각 경우의 수에 대한 참과 거짓이 AND 연산으로 엮이게 된다. 이런 경우, 조건문의 조건 부분에 서술되는 내용이 너무 길어져 가독성이 매우 떨어지게 된다.

 

이렇게 연관된 조건이 많은 문제의 경우, 가장 특수한 경우의 수를 먼저 떠올리는 것이 중요하다. 해결하려는 문제 유형에 따라 주어진 조건에 모두 해당되지 않는 경우 혹은 모두 해당되는 경우가 가장 특수한 경우의 수가 될 수 있겠다. 이는 각 조건이 어떠한 입력값에 따라 결과물을 출력하도록 유도하는 일종의 필터 역할을 수행한다고 생각하면 이해하기 편하다. 우리는 이런 필터링에도 불구하고 걸러지지 않는 불순물과 같은 특수한 경우를 먼저 생각하고, 이를 대처할 코드를 작성하는 것과 같다.

 

다음은 각 경우에 대하여 비교한 결과를 반환하는 코드이다.

bool compare(pair<string, int> &a, pair<string, int> &b) {
    if (a.second == b.second) {
        if (a.first.length() == b.first.length()) {
            return a.first < b.first;
        }
        return a.first.length() > b.first.length();
    }
    return a.second > b.second;
}

 

작성자의 경우, 주어진 조건에 모두 해당하지 않는 경우에 먼저 집중하여 함수를 작성하였다.

 

문제에서 주어진 조건에 모두 해당하지 않는 경우는 두 단어의 빈도수가 같고, 각 단어의 길이가 같을 때 각 단어의 사전 상 순서이다. 이때 조건문을 중첩 조건문을 활용하여 작성했는데, 이렇게 작성할 경우 굳이 모든 조건에 대하여 else if나 else를 사용할 필요 없이 각 경우에 대하여 마치 AND 연산을 활용한 것처럼 조건의 중첩 표현만으로 작성할 수 있다.

 

즉, if 안의 if는 ( 외부 if문 ) && ( 내부 if문 )과 같은 결과를 도출하게 된다.

 

다음은 전역 변수 및 main 함수 부분이다.

void fast_io() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

int N = 0, M = 0;
map<string, int> word_map;
    
int main() {
    fast_io();
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string word;
        cin >> word;
        if (word.length() >= M) {
            word_map[word]++;
        }
    }

    vector<pair<string, int>> word_vec(word_map.begin(), word_map.end());
    sort(word_vec.begin(), word_vec.end(), compare);

    for (auto it : word_vec) {
        cout << it.first << "\n";
    }
}

 

main 함수 설명에 앞서 fast_io 함수에 대해 간단히 소개하자면, 입출력 시간을 절약할 수 있는 코드이다. 여러 알고리즘을 해결할 때 많이 사용하며, 실제로 해당 문제 페이지의 하단에는 해당 코드를 활용하도록 권장하고 있다.

 

조건 1번을 해결하기 위해선 입력된 단어와 해당 단어의 빈도수를 저장할 수 있는 자료구조가 필요하다. 따라서 각각 string과 int 형태로 저장할 수 있는 map 자료구조를 활용하여 word_map을 생성했다..

 

다음으로 vector 자료구조이다. 이때 왜 map을 그대로 사용하지 않고 굳이 vector를 활용했는지 의문일 수 있다.

 

C++에서의 map은 트리(Tree)를 활용하여 만들어졌다. 정확히는 레드 블랙 트리라는 자가 균형 이진 탐색 트리를 활용하여 트리 구조가 데이터 삽입 삭제시 편향화되는 것을 방지하도록 설계된 자료구조이다. 

 

즉, 순서를 사용자가 임의로 변경할 수 없는 자료구조이다. 따라서 이번 문제 해결에 활용되는 sort와 같은 순서 변경 알고리즘을 사용할 수 없는 자료구조이기에, 원소의 위치 변경에 대하여 자유로운 vector를 활용하게 되었다.

 

sort 함수에 대해 설명하자면 기본적인 작성 방식은 다음과 같다.

 

sort(begin, end, comparing_method)

 

함수의 첫 번째 파라미터는 사용자가 순서를 정렬하고 싶은 자료구조 내부에서의 시작 지점, 두 번째 파라미터는 종료 지점이다. 앞의 두 파라미터를 통해 자료구조 내에서 순서를 정렬하고자 하는 구역을 지정할 수 있다.

 

세 번째 파라미터는 method라고 작성했지만, 사실 이 부분의 작성 여부는 선택 사항이다. 작성자와 같이 특정 조건에 따라 정렬하고 싶다면 활용하면 된다. 코드를 보면 알겠지만, 문제에서 주어진 조건에 따른 비교 결과를 반환하는 함수인 compare를 입력했다.

 

마지막으로 자료구조를 순회하는 이터레이터(Iterator)를 it변수로 할당하여 word_vec의 각 { key : value } 쌍의 내용 중 문제에서 요구하는 결과값인 key값을 출력하도록 for문을 실행하는 것으로 코드는 종료된다.