[BOJ 백준] 14426번 접두사 찾기

문제

BOJ 14426 : https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

접근

 이 문제는 입력으로 주어지는 N과 M의 최댓값이 10,000이고, 각각의 문자열의 최대 길이도 500밖에 안되기 때문에 단순하게 조합 가능한 모든 문자열을 대입해 해결하는 브루트 포스(brute force)로 해결할 수 있다.

 하지만 나는 수행 시간을 단축하기 위해 이분 탐색(Binary Search)을 이용하여 문제를 해결하였다. 먼저 이분 탐색을 위해 문자열의 집합 S에 대해 sort를 해준다. 후에 입력받은 임의의 문자열에 대해 이분 탐색을 수행하면 된다.

 이때 <iostream>의 표준 입출력을 사용해 코드를 짜는데 시간을 더욱 줄이고자 한다면 아래의 코드를 추가해주자. 위의 제출 결과에서 확인할 수 있듯이 약 5배나 시간을 단축할 수 있었다. 이는 문제에서 입력이 최대 20,002번 있을 수 있기 때문이다.

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

 <iostream>의 입출력에 관한 설명은 이 글(https://algoribi.tistory.com/134)의 '번외- 시간 초과의 원인' 부분을 참고하길 바란다.

 

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, ans = 0;
    cin >> n >> m;

    string s;
    vector<string> str;
    for (int i = 0; i < n; i++) {
        cin >> s;
        str.push_back(s);
    }
    sort(str.begin(), str.end());

    for (int i = 0; i < m; i++) {
        cin >> s;
        int left = 0, right = str.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (str[mid].substr(0, s.size()).compare(s) == 0) {
                ans++;
                break;
            }
            if (str[mid].compare(s) > 0)
                right = mid - 1;
            else if (str[mid].compare(s) < 0)
                left = mid + 1;
        }
    }
    cout << ans;

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study