[BaekJoon/백준] 1764번 C++

두 문자열 목록 중 겹치는걸 찾는 문제다.

 

찾기를 시도할 때 find 함수를 시간복잡도 O(N)으로 하게 되면

총 시간복잡도가 O(N^2)이 되어서 시간초과가 날 것이다.

 

이 문제는 이진탐색 = 이분탐색을 시도해야한다.

 

실수할 수 있는 점은, '문제에서 출력 결과를 사전순으로 요청한 것'

여기서 나도 틀렸다.

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

using namespace std;

vector <string> str;
vector <string> result;
int N, M;

bool compare(string a, string b) {
    return a < b;
}

bool bin_search(int n, string key) {
    
    int pl = 0;
    int pr = n - 1;
    int pc;
    do {
        pc = (pl + pr) / 2;
        
        if(str[pc] == key)
            return true;
        else if(str[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while(pl <= pr);
    
    return false;
}

int main() {
    int i;
    string temp;
    
    ios::sync_with_stdio();
    cin.tie(NULL);
    
    cin >> N >> M;
    
    for(i = 0; i < N; i++) {
        cin >> temp;
        str.push_back(temp);
    }
    
    sort(str.begin(), str.end(), compare);
    
    for(i = 0; i < M; i++) {
        cin >> temp;
        if(bin_search(N, temp))
            result.push_back(temp);
    }
    
    sort(result.begin(), result.end(), compare);
    cout << result.size() << '\n';
    for(i = 0; i < result.size(); i++) {
        cout << result[i] << '\n';
    }
}

 

 

참고 :

www.acmicpc.net/board/view/53196 

jaimemin.tistory.com/672