Archive / random-solve / C++

26226번 Autocomplete

문제

26226번 Autocomplete - 백준

설계

앗 영어 문제

단어를 비교하는 문제이다.
두 단어가 “비슷하다”고 말하는 조건은 다음과 같다.

대소문자 구분 없이 비교했을 때 완전히 같음
대소문자를 구분하면 서로 다른 문자의 위치가 K개 이하

단어의 길이 최대 2000, 단어 사전 1000개, 질의 1000개다.
생각보다 숫자가 좀 크다?

구현

1. 시간 초과의 역사

2000 * 1000 * 1000 = 2000000000
이런 미친 숫자가!

문제의 제한시간은 1초다.
탐색범위를 최대한 줄여야한다.
K는 최대 5기 때문에 빠른 탈출 트리거로 사용할 수 있는데
나머지 숫자는 커서 잘 생각해야한다.

아래는 시간 초과난 경우

문자열 전체 비교하면 터져서 소문자 변환 후 별도 저장했지만 터짐
마스킹 처리 후 비트기반 xor 연산했지만 터짐
K가 작기 때문에 가능한 모든 마스크 조합을 만들어봤지만 터짐
bitset 구조로 바꿨는데 터짐
다 때려치우고 소문자 정렬 후 이진탐색했는데 터짐

결국 초심으로 돌아가 단순하게 후보군 필터링 후 해시 기반 탐색하니 통과되었다.

2. 입력 받아 필터링 후 탐색

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, W, Q;
    cin >> K >> W;

    // 소문자 + 길이 기준
    unordered_map<string, unordered_map<int, vector<string>>> words;

    for (int i = 0; i < W; ++i) {
        string word;
        cin >> word;

        string lower = toLower(word);
        int length = word.size();

        words[lower][length].push_back(word);
    }

    cin >> Q;

    for (int i = 0; i < Q; ++i) {
        string query;
        cin >> query;

        string lowerQuery = toLower(query);
        int length = query.size();
        int result = 0;

        // 소문자 + 길이 일치하는 단어만 대상으로 필터링
        if (words.count(lowerQuery) && words[lowerQuery].count(length)) {

            const vector<string>& list = words[lowerQuery][length];

            for (const string& target : list) {
                int cnt = caseDifference(query, target, K);
                if (cnt <= K) {
                    result++;
                }
            }
        }

        cout << result << '\n';
    }

    return 0;
}

채점

반성

괜시리 머리 굴려서 살 붙이며 비대해지는 것 보다 가끔은 초심으로 돌아갈 필요가 있다.

그건 그렇고 왜 쉬운 문제는 안나오지?
처음에 조건보고 할만한데? 하고 덤볐다가 피봤다.

코드 확인

Link to GitHub