백준 4158번 CD :: 마이구미

이 글은 백준 알고리즘 문제 4158번 "CD" 에 대한 문제를 풀이한다.

이 문제를 풀기위해 특정 알고리즘에 대한 지식은 필요하지 않다.

정답 비율이 20%대뿐만 아니라, 제출수가 많지 않은 문제이다.

하지만 단순히 문제를 이해하고, 그것에 대해 논리적 사고만으로 충분히 풀 수 있는 문제이다.

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

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

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

문제에서 주의할 점은 "입력은 여러 개의 테스트 케이스로 이루어져 있다" 를 인지해야한다.

본인 또한 이것을 확인하지 않아, 멘붕이 왔었다.

결국 같은 CD의 개수를 찾으면 되는 문제가 된다.

이진탐색과 같은 탐색 알고리즘을 요구하지 않는다.

문제는 오름차순으로 주어지는 것을 활용하면 쉽게 해결할 수 있다.

다음과 같은 입력이 주어졌을 경우를 보자.

1 2 4 10
1 4 10 13

우선 index가 0인 지점부터 상근이와 선영이를 비교한다.

1 2 4 10
1 4 10 13

같은 번호를 가졌으니 카운트는 하나 올라가게 된다.

그리고 두 번호는 더이상 비교할 필요가 없으니 모두 인덱스를 하나 증가시킨다.

1 2 4 10
1 4 10 13

다음 인덱스에서 서로 번호가 같지 않다.

그렇다면, 그 다음 비교는 어떻게 해야할까?

이전처럼 상근이와 선영이의 인덱스 모두를 증가시키면 안된다.

증가시킨다면, 번호가 4인 경우를 찾지 못하게 된다.

여기서 오름차순으로 주어진 것을 활용할 수 있게 된다.

비교한 두 수에서 작은 수를 가진 사람의 인덱스를 증가시키는 것이다.

작은 수를 가진 사람이 다음 수들 중 현재 비교 대상이 있을 수 있기 때문이다.

그리고 둘 배열 중 하나라도 끝지점에 도달하면 더이상 비교할 필요가 없게 된다.

1 2 4 10
1 4 10 13

1 2 4 10
1 4 10 13

1 2 4 10
1 4 10 13

1 2 4 10
1 4 10 13

문제를 잘 파악한 후 접근했다면, 어려움 없이 쉽게 풀 수 있는 문제가 된다.

private void solve() {
    StringBuilder sb = new StringBuilder();
    while(true) {
        int n = sc.nextInt();
        int m = sc.nextInt();
 
        if (n == 0 && m == 0) {
            System.out.println(sb.toString());
            return;
        }
 
        int[] a = new int[n];
        int[] b = new int[m];
        int positionA = 0, positionB = 0;
        int ans = 0;
 
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
 
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
 
        while(true) {
            if (positionA == n || positionB == m) {
                break;
            }
 
            if (a[positionA] < b[positionB]) {
                ++positionA;
            } else if (a[positionA] > b[positionB]) {
                ++positionB;
            } else {
                ++positionA;
                ++positionB;
                ++ans;
            }
        }
        sb.append(ans + " ");
    }
}