[백준 14426번] 접두사 찾기 (C++)

문제링크 : https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, cnt = 0;
vector<string>v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=0; i<N; i++)
    {
            string s;
            cin >> s;
            v.push_back(s);
    }
    sort(v.begin(), v.end()); //이분탐색을 위한 정렬

    for(int i=0; i<M; i++)
    {
        string s;
        cin >> s;
        int l=0, r=N-1;
        while(l<=r)
        {
            int target = (l+r)/2;

            if(s < v[target]) r = target - 1;
            else if(s > v[target]) l = target + 1;
            
            if(v[target].substr(0, s.size())==s) //포함하는지 체크
            {
                cnt++;
                break;
            }
        }
    }

    cout << cnt;
}

 

부분 문자열을 체크하는 문제이다.

처음에 N이 10000인 것을 보고 단순하게 이중반복문으로 풀어도 상관없을 것이라고 생각했으나 substr을 사용하는 과정에서 추가적인 시간이 소요되는 것을 모르고 시간초과를 겪다가 이분탐색을 이용하게 되었다.

 

이분탐색을 위해 문자열 집합을 정렬해주고 시작한다.

이후 접두사를 체크할 문자열을 입력받고 바로 이분탐색을 통해 target 값을 탐색한다.

substr을 통해서 문자열 포함 여부를 체크하여 카운팅했다.

 

substr을 쓸 때마다 느끼는 건데 substr은 정해라기보단 이런 방법도 있다에 가까운 느낌을 많이 받는 것 같다.

정해에 가장 가까운 것은 트라이를 이용하는 것 같다.