백준 4158 CD [c++]

17 Jun 2022 in Develop / Solving

c++

문제 분석

• 상근이, 선영이가 각각 N, M개 CD를 가지고 있음.
• N개의 줄에 걸처 상근이가 가지고 있는 CD의 번호,
  M개의 줄에 걸쳐 선영이가 가진 CD의 번호가 주어짐.(둘 다 오름차순)
• CD의 번호는 10억을 넘지 않음.

• 두 사람이 동시에 가지고 있는 CD를 팔 때, 최대로 팔 수 있는 양은?

• 여러 개의 테스트 케이스로 구성됨.
  • N, M이 0 0이면 프로그램 종료.

입력조건

N, M이 0 0이 아닐 때까지 반복 {

	상근이 CD 수 N, 선영이 CD 수 M
	N줄에 걸쳐 {
		상근이가 가진 CD 번호(오름차순)
	}
	M줄에 걸쳐  {
		선영이가 가진 CD 번호(오름차순)
	}
} 

풀이과정

• 집합을 이용하였다.
• c++의 unordered_set을 이용하여, 상근이의 CD번호를 전부 저장한 뒤,
• 선영이의 CD를 하나씩 입력받으면서, set에 들어있으면 팔 수 있다고 체크하였다.
• 체크한 수를 출력하면 정답.

추가

투 포인터 + 이분탐색으로 진행하려고 하였으나, 얄짤없이 시간초과가 떠버린다. 이분탐색으로 통과된 코드가 있던데 도데체 어떻게 한건지 모르겠다. ㄷㄷ

전체 코드

• 통과한 코드

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    do {
        int N, M;
        cin >> N >> M;
        // 0 0 입력에 프로그램 끝내기.
        if(N == 0 && M == 0) return 0;

        unordered_set<int> pi;

        for(int i = 0; i < N; i++) {
            int num;
            cin >> num;
            pi.insert(num);
        }

        int ans = 0;
        for(int i = 0; i < M; i++){
            int num;
            cin >> num;
            if(pi.find(num) != pi.end()) ans++;
        }
        cout << ans << endl;

    } while(true);
}

• 투포인터 + 이분탐색 코드(시간 초과)

#include <iostream>

using namespace std;

int binarysearch(int arr[], int st, int ed, int goal) {
    int mid = (st+ed)/2;
    while (st < ed) {
        if(arr[mid] < goal) st = mid+1;
        else if(arr[mid] > goal) ed = mid-1;
        else return mid;
    }
    return ed;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    do {
        int N, M;
        cin >> N >> M;
        if(N == 0 && M == 0) return 0;

        int a[N];
        int b[M];

        for(int i = 0; i < N; i++) cin >> a[i];
        for(int i = 0; i < M; i++) cin >> b[i];
        
        int apointer = 0;
        int bpointer = 0;

        int ans = 0;
        while( apointer < N && bpointer < M) {
            if     (a[apointer] < b[bpointer]) apointer = binarysearch(a, apointer, N, b[bpointer]);
            else if(a[apointer] > b[bpointer]) bpointer = binarysearch(b, bpointer, M, a[apointer]);

            if (a[apointer] == b[bpointer]){
                ans ++;
            }
            
            apointer++;
            bpointer++;
        }
        cout << ans << endl;

    } while(true);
}

추가…

자바로는 그냥 이렇게 통과한다…. 허무

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class BJ4158_CD {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            if(N == 0 && M == 0) break;

            HashSet<Integer> set = new HashSet<>();
            for(int i = 0; i < N+M; i++){
                set.add(Integer.parseInt(br.readLine()));
            }
            sb.append(N + M - set.size() + "\n");
        }
        System.out.print(sb);
    }
}