← 문제 풀이 목록

백준 20920: 영단어 암기는 괴로워

/ 11분 분량 / 문제 풀이
#알고리즘#백준#코딩테스트

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 단어 목록에서 특정 조건을 만족하는 단어를 정렬하여 출력하는 문제입니다.

백준 20920: 영단어 암기는 괴로워

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 단어 목록에서 특정 조건을 만족하는 단어를 정렬하여 출력하는 문제입니다.

문제 소개

  • 문제 번호: 20920
  • 문제명: 영단어 암기는 괴로워
  • 난이도: Silver III
  • 사용 언어: C++
  • 실행 시간: 836 ms
  • 메모리: 13928 KB
  • 문제 요약: 여러 단어가 주어질 때, 빈도가 높은 단어, 길이가 긴 단어, 알파벳 순서대로 단어를 정렬하여 출력하는 문제입니다. 이때, 길이가 M 이상인 단어들만 출력합니다.

접근 방법

문제를 해결하기 위해 다음과 같은 자료구조와 알고리즘을 사용했습니다.

  1. 단어 빈도 계산: 입력된 단어들의 빈도를 효율적으로 세기 위해 std::map<std::string, int>를 사용했습니다. map은 문자열을 키로, 해당 문자열의 빈도를 값으로 저장하며, 키의 중복을 허용하지 않고 자동으로 정렬하는 특징이 있습니다.
  2. 정렬 기준 정의: 문제에서 요구하는 정렬 순서는 다음과 같습니다.
    • 빈도가 높은 단어일수록 앞에 배치
    • 빈도가 같으면 길이가 긴 단어일수록 앞에 배치
    • 빈도와 길이가 모두 같으면 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치
      이러한 복합적인 정렬 기준을 적용하기 위해 std::sort 함수와 함께 사용자 정의 비교자(comparator)를 구현했습니다.
  3. 중복 제거: 정렬 후에는 중복된 단어를 제거해야 합니다. std::unique 함수와 vector::erase 멤버 함수를 사용하여 정렬된 벡터에서 중복된 원소를 효율적으로 제거했습니다.
  4. 조건부 출력: 마지막으로, 길이가 M 이상인 단어들만 표준 출력으로 출력했습니다.

이 방법을 선택한 이유는 다음과 같습니다.

  • std::map은 단어의 빈도를 효과적으로 계산하고 관리하는 데 적합합니다.
  • 사용자 정의 비교자를 사용하면 복잡한 정렬 규칙을 명확하게 구현할 수 있습니다.
  • std::unique와 vector::erase 조합은 정렬된 데이터에서 중복을 제거하는 표준적인 방법입니다.

풀이 과정

  1. 입력 받기: 두 개의 정수 N (단어의 개수)과 M (외울 단어의 길이 기준)을 입력받습니다.
  2. 단어 저장 및 빈도 계산: N개의 단어를 입력받아 std::vector<std::string>에 저장하고, 동시에 std::map<std::string, int>를 사용하여 각 단어의 빈도를 계산합니다. map의 operator[]를 사용하면 키가 존재하지 않을 경우 자동으로 생성하고 0으로 초기화한 후 1을 더하므로 편리하게 빈도를 누적할 수 있습니다.
  3. 사용자 정의 비교자 구조체 정의: Compare라는 구조체를 정의하고, std::map의 참조를 멤버 변수로 받습니다. 이 구조체는 operator()를 오버로딩하여 두 문자열 a와 b를 비교하는 로직을 구현합니다. 비교 로직은 문제에서 요구하는 빈도, 길이, 알파벳 순서대로 수행됩니다.
  4. 단어 정렬: std::sort 함수를 사용하여 vector에 저장된 단어들을 Compare 구조체로 정의된 비교 기준에 따라 정렬합니다.
  5. 중복 제거: std::unique 함수를 호출하여 정렬된 벡터에서 중복된 단어를 제거합니다. unique 함수는 중복되지 않는 원소들의 끝을 가리키는 반복자를 반환하며, vector::erase를 사용하여 실제 중복 원소들을 벡터에서 제거합니다.
  6. 결과 출력: 정렬 및 중복 제거가 완료된 벡터를 순회하며, 단어의 길이가 M 이상인 경우에만 해당 단어를 표준 출력으로 출력합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;

struct Compare {
    const map<string, int>& word_freq;
    // 멤버변수 word_freq가 wf로 받은 메인 함수의 word_freq를 참조
    Compare(const map<string, int>& wf) : word_freq(wf) {}
    
    // 자주 나오는 단어일수록 앞에 배치한다. <- map(키, 밸류 형태/정렬상태)과 map의 at 메서드 사용. [키]로 키의 밸류 접근시 존재하지 않는 키(워드)면 임의로 map에 새 키가 만들어질 수 있어 사용 자제. 
    // 해당 단어의 길이가 길수록 앞에 배치한다. <- length() 사용
    // 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 <- a < b
    bool operator()(const string& a, const string& b) const {
        if (word_freq.at(a) != word_freq.at(b)) return word_freq.at(a) > word_freq.at(b);
        if (a.length() != b.length()) return a.length() > b.length();
        return a < b;
    }
};

int main(){
    // 단어의 개수 N, 외울 단어의 길이 기준이 되는 M
    int N; int M;
    cin >> N >> M;
    
    vector<string> words;
    
    while(N--) {
        string word;
        cin >> word; // 입력은 알파벳 소문자로만 주어지며 단어의 길이는 
                     // 10을 넘지 않는다.
                     // 단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.
        words.push_back(word);
    }
    
    map<string, int> word_freq;
    // 키들과 0 입력
    // map은 자동으로 [word]로 접근 시 키 word가 없으면 word, 0으로 생성됨
    // 입력된 단어 등장할 때마다 해당 단어 카운트 증가
    for(const string& word : words) {
        word_freq[word]++;  // map에는 push_back이 없고 한 줄로 충분
    }

    // sort()는 내부적으로 두 원소를 비교할 때마다 비교자를 호출한다.
    // Compare(word_freq)는 생성자 호출.
    // 비교자는 메인의 지역변수 word_freq를 멤버변수인 word_freq으로 입력받은 상태다.
    // 그래서 sort함수가 words 벡터의 두 원소를 골라서 
    // Compare의 () 연산자를 호출하면 
    // 이미 Compare 객체는 메인의 word_freq을 인자로 받아서 alias를 가지고 있으니 
    // () 연산자 호출 시 alias로 접근하여 정렬기준에 부합하게 true, false를 반환한다.
    // sort()가 true/false에 따라 words 배열을 재배열한다.
    sort(words.begin(), words.end(), Compare(word_freq));
    
    // unique()는 정렬된 배열에서 중복된 원소를 뒤로 밀어내고, 고유 원소들만 가진 벡터가 생겼다 할 때에 그 고유 원소들만 가진 벡터의 end()를 반환한다.
    // 그러면 그 고유 원소 구간의 end()와 원래 words의 end()를 인자로 사용해 
    // 중복된 원소들은 erase()로 제거한다. -> 고유 원소들만 남긴다.
    words.erase(unique(words.begin(), words.end()), words.end());
    
    // 정답 출력
    for(const string& word : words) {
        if(word.length() >= M) {  // M 이상인 단어만
            cout << word << '\n';
        }
    }
}

복잡도 분석

  • 시간 복잡도:

    • 단어 입력 및 std::vector에 저장: O(N * L), 여기서 N은 단어의 개수, L은 단어의 최대 길이입니다.
    • 단어 빈도 계산 (std::map 사용): O(N * L * log N), map에 삽입/접근 시 O(L * log N)이 걸립니다.
    • std::sort: O(N log N * C), 여기서 C는 비교 연산의 복잡도입니다. 비교 연산은 최대 O(L)이 걸릴 수 있습니다. 따라서 전체적으로 O(N log N * L)입니다.
    • std::unique: O(N * L), 중복을 확인하며 이동시키는 과정입니다.
    • 결과 출력: O(N * L)
      종합적으로, O(N log N * L) 입니다.

  • 공간 복잡도:

    • std::vector<std::string> words: O(N * L)
    • std::map<std::string, int> word_freq: O(N * L)
      종합적으로, O(N * L) 입니다.

배운 점

이 문제를 풀면서 다음과 같은 내용을 배웠습니다.

  1. 복합적인 정렬 기준 처리: std::sort 함수와 사용자 정의 비교자를 활용하여 빈도, 길이, 알파벳 순서 등 여러 기준을 조합하여 데이터를 정렬하는 방법을 익혔습니다. 특히 operator() 오버로딩을 통해 비교 로직을 함수처럼 사용할 수 있다는 것을 알게 되었습니다.
  2. std::map의 활용: 문자열의 빈도를 효율적으로 계산하고 관리하기 위해 std::map을 사용하는 것이 매우 유용하다는 것을 다시 한번 확인했습니다. operator[]를 사용하여 키가 없어도 자동으로 생성하고 값을 초기화하는 편리성을 경험했습니다.
  3. std::unique와 vector::erase 조합: 정렬된 컨테이너에서 중복된 요소를 제거하는 표준적인 방법을 익혔습니다. std::unique가 반환하는 반복자를 vector::erase에 전달하여 중복 요소를 실제로 제거하는 과정을 이해했습니다.
  4. const 참조의 중요성: 사용자 정의 비교자에서 word_freq를 const 참조로 받아와 불필요한 복사를 방지하고, 원본 데이터에 대한 안전성을 확보하는 방법을 배웠습니다. at() 메서드를 사용하여 const 참조로도 안전하게 map의 요소에 접근할 수 있음을 알게 되었습니다.