백준 4158 CD

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

4158번: CD

상근이가 가진 CD의 목록, 선영이가 가진 CD의 목록이 각각 오름차순으로 주어질 때,

두 사람이 공통으로 갖고있는 CD의 갯수를 찾는 문제다.

 

시간초과 코드 / 통과 코드는 아래에

상근이의 CD 목록을 set에 넣고, 선영이의 CD 목록을 차례로 순회하며 특정 CD가 상근이의 목록에도 있는지 확인하는 코드다.

문제를 읽고 바로 무난하게 통과하겠거니~ 제출했는데 시간초과가 나왔다.

 

0. 시간제한 1초 >> 연산 수 대략 1억으로 잡는다.

1. 상근이와 선영이의 CD목록의 크기는 각각 최대 100만이다.

2. CD의 번호는 최대 10억이다.

3. CD의 목록은 이미 정렬되어있다.

 

해당코드에 크기가 100만인 코드를 넣는 상황을 생각해보자. ( O(n*log(n)), n = 100만))

상근이의 목록 set에 100만개를 삽입한다고 한다면,

=>100만 x log(100만) = 2000만

선영이의 목록을 순회하며 100만개를 찾는다고 하면,

=> 100만 x log(100만) = 2000만

총 4000만의 연산 수가 나온다. (1억의 반도 못미친다~)

왜 시간초과가 났을까?

입력은 여러 개의 테스트 케이스로 이루어져 있다.

일단 이것보다 빠른 해법이 존재한다는 것이다.

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

#include <set>
int main(){
    fio;
    int N, M;
    //
    while(1){
        cin >> N >> M;
        if(N == 0 && M == 0) break;
        set<int> SK;
        for(int i=0; i< N; i++){
            int tmp; cin >> tmp;
            SK.insert(tmp);
        }
        int cnt = 0;
        for(int i =0; i<M; i++){
            int tmp; cin >> tmp;
            if(SK.find(tmp) != SK.end()){//있다
                cnt++;
            }
        }
        cout << cnt<<'\n';
    }
    return 0;
}

최종 코드

힐끗 보고 넘겨버린 3번 조건, "CD의 목록은 이미 정렬되어있다." 

굳이 상근이의 CD 목록을 set에 넣으며 각 항목에 O(log(n))의 시간을 쓸 이유가 없다.

1. 정렬된 순서 그대로 vector에 넣어 놓고 (O(n*1)) = O(n)

2. 선영이의 CD 목록을 순회하며 각각의 값을 상근이의 vector에서 이분탐색하면 된다! => O(n*log(n))

 

상근이 과정의 시간복잡도가 O(n*log(n)) 에서 O(n)으로 줄었다.

총 4000만에서 2100만으로 연산수가 많이 줄었다.

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

#include <vector>
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;
}