백준 4158 CD (자료구조 실버 5)

문제

상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. CD의 번호는 십억을 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0 0이 주어진다.

상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다.

출력

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

내 제출

#include <iostream>
#include <vector>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
    fio;
    int N, M;
    while(1){
        cin >> N >> M;
        if(N == 0 && M == 0) break;
        vector<int> SK(N, 0); 
        for(int i= 0; i < N; i++)   cin >> SK[i];
        int cnt = 0;
        for(int i = 0; i < M; i++){
            int tmp; cin >> tmp;
            //
            int left_idx = 0, right_idx = SK.size()-1;
            while(left_idx <= right_idx){
                int mid_idx = (left_idx + right_idx)/2;
                if(SK[mid_idx] == tmp){
                    cnt++;
                    break;
                }else if(SK[mid_idx] > tmp){
                    right_idx = mid_idx-1;
                }else{
                    left_idx = mid_idx+1;
                }
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

이번 문제도 생각 안 하고 풀면 시간초과로 오답처리된다.

여기서 중요한 점은 문제에서 CD의 목록이 이미 정렬되었다고 알려준 것이다.

 

1. 정렬된 순서 그대로 vector에 넣는다.

2. 선영이의 CD 목록을 순회하며 각각의 값을 상근이의 vector에서 이분탐색한다.

이렇게 하면 그냥 반복문을 사용하는 것보다 빨리 처리할 수 있다.

 

vector는... 생소하지만 자료구조를 하려면 좀 쓸 줄 알아야 하는 것 같다...