[BOJ] Auto-Complete

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

BOJ - Auto-Complete

문제 유형: 문자열 처리, 정렬, 이진탐색

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 128MB

 

문제

Bessie the cow has a new cell phone and enjoys sending text messages, although she keeps making spelling errors since she has trouble typing on such a small screen with her large hooves. Farmer John has agreed to help her by writing an auto-completion app that takes a partial word and suggests how to complete it.

The auto-completion app has access to a dictionary of W words, each consisting of lowercase letters in the range a..z, where the total number of letters among all words is at most 1,000,000. The app is given as input a list of N partial words (1 ≤ N ≤ 10000), each containing at most 1000 lowercase letters. Along with each partial word i, an integer K_i is also provided, such that the app must find the (K_i)th word in alphabetical order that has partial word i as a prefix. That is, if one ordered all of the valid completions of the ith partial word, the app should output the completion that is (K_i)th in this sequence.

 

Bessie는 오타를 많이 낸다.

John은 자동완성 앱을 만들어주기로 한다.

 

앱은 단어장 데이터에 접근할 수 있는데, 단어장에는 영문소문자로 된 단어들이 구성되어 있고, 모든 단어들의 글자의 합이 최대 1,000,000이다.

앱은 N개의 부분단어들로 주어지는데, 각각 최대 1000글자까지 있다.

K_i도 같이 주어지는데, 부분단어를 prefix로 하는 단어들 주에서 K_i번째 단어를 자동완성 시켜줘야 한다.

 

입력

• Line 1: Two integers: W and N.
• Lines 2..W+1: Line i+1: The ith word in the dictionary.
• Lines W+2..W+N+1: Line W+i+1: A single integer K_i followed by a partial word.

첫째 줄에 W와 N이 주어집니다.

두 번째 줄부터 W+1번 줄까지 단어장의 i번째 단어가 주어집니다.

W+2부터 W+N+1까지 K_i와 부분단어가 공백으로 구분되어 주어집니다.

 

출력

• Lines 1..N: Line i should contain the index within the dictionary (an integer in the range 1..W) of the (K_i)th completion (in alphabetical order) of the ith partial word, or -1 if there are less than K_i completions.

각 N개의 줄에 K_i, 부분단어에 대한 자동완성 단어의 사전 내 인덱스를 출력하시오. 해당하는 게 없으면 -1을 출력하시오.

 

풀이

단어들을 받아서 <단어> -> <인덱스>로 변환해주는 해시맵을 구성하고, 단어 리스트는 정렬해준다.

그 뒤, 각 쿼리에 대해서, 이진탐색을 통해(lower_bound)를 통해서, 해당 prefix를 가지는 맨 앞의 위치로 온다.

거기서 k-1을 더한 인덱스가 목표 단어가 된다.

만약 그 단어가 prefix가 맞다면, 유효하므로 그 단어의 기존 인덱스를 출력해주고, 아니라면 -1을 출력한다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

bool isprefix(string &pref, string &str) {
    if (pref.size() > str.size()) return false;
    for (int i = 0; i < pref.size(); i++) {
        if (pref[i] != str[i]) return false;
    }
    return true;
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int w, n;
    cin >> w >> n;

    vector<string> dict(w);
    unordered_map<string, int> word2idx;
    for (int i = 0; i < w; i++) {
        cin >> dict[i];
        word2idx[dict[i]] = i + 1;
    }
    sort(dict.begin(), dict.end());

    for (int i = 0; i < n; i++) {
        int k;
        string p;
        cin >> k >> p;

        int lb = lower_bound(dict.begin(), dict.end(), p) - dict.begin();
        int idx = lb + k - 1;

        if (idx < w && isprefix(p, dict[idx])) {
            cout << word2idx[dict[idx]] << "\n";
        } else {
            cout << "-1\n";
        }
    }

    return 0;
}