백준 영단어 암기는 괴로워 (20920번) C++

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

문제

• 단어 N개가 주어진다.
• 길이가 M 이상인 단어만 암기 대상이다.
• 단어의 정렬 기준은 다음과 같다:
1. 많이 등장한 단어가 먼저
2. 단어 길이가 길수록 먼저
3. 사전순으로 앞선 단어가 먼저
• 출력은 정렬된 단어들을 한 줄씩 출력한다.

---

테스트케이스

입력 1

7 4
apple
ant
sand
apple
append
sand
sand

출력 1

sand
apple
append

입력 2

12 5
appearance
append
attendance
swim
swift
swift
swift
mouse
wallet
mouse
ice
age

출력 2

swift
mouse
appearance
attendance
append
wallet

---

문제작동원리

1. 단어를 입력받으면서 길이가 M 이상인지 확인한다.
2. 단어 빈도를 세기 위해 unordered_map을 사용한다.
   • 키는 구조체 Word (char 배열로 저장)
   • 값은 등장 횟수
   • 커스텀 해시 함수와 동등 비교 함수 정의 필요
3. 모든 단어를 arr[]에 옮겨 담은 뒤 sort()로 정렬한다.
4. 정렬 기준:
   • 등장 횟수 N (내림차순)
   • 길이 len (내림차순)
   • 사전순 (오름차순)

---

아이디어

• 선형 탐색으로 단어를 찾으면 \(O(N^2)\) → 시간초과
• 따라서 해시 기반 unordered_map으로 단어 카운트를 관리 → 평균 \(O(1)\)
• 이후 정렬은 \(O(K \log K)\) (K = 서로 다른 단어 개수)
• 총 시간 복잡도: \(O(N \log K)\) → 충분히 통과

---

전체코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct Word
{
    char arr[100];
    int N=0;
    int len=0;
    
    bool operator<(const Word& other) const
    {
        if (N != other.N)
            return N > other.N; // 빈도 내림차순
        if (len != other.len)
            return len > other.len; // 길이 내림차순
        return strcmp(arr, other.arr) < 0; // 사전순 오름차순
    }
};

struct WordHash {
    size_t operator()(const Word& w) const {
        unsigned long h = 0;
        const char* s = w.arr;
        while (*s) h = h * 131 + *s++;
        return h;
    }
};

struct WordEqual {
    bool operator()(const Word& a, const Word& b) const {
        return strcmp(a.arr, b.arr) == 0;
    }
};

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    unordered_map<Word, int, WordHash, WordEqual> s;
    Word arr[100000]; // 최대 크기 맞춤
    int N, M;
    cin >> N >> M;
    
    for(int i = 0; i < N; i++)
    {
        Word str;
        cin >> str.arr;
        str.len = strlen(str.arr);
        if (str.len >= M) s[str]++; // M 이상만 저장
    }
    
    int idx = 0;
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        strcpy(arr[idx].arr, it->first.arr);
        arr[idx].N = it->second;
        arr[idx].len = it->first.len;
        idx++;
    }
    
    sort(arr, arr + idx);
    
    for (int i = 0; i < idx; i++)
        cout << arr[i].arr << "\n";
        
    return 0;
}

---

결론

• unordered_map을 사용해 단어 빈도 집계를 \(O(N)\)으로 처리할 수 있다.
• 커스텀 해시/비교 함수를 정의해야 사용자 정의 타입 Word를 키로 쓸 수 있다.
• 정렬은 sort()와 operator< 정의로 해결한다.
• 이렇게 하면 BOJ 20920번 문제를 시간 초과 없이 해결할 수 있다.