• 백준 4158번 CD :: 마이구미
    알고리즘 풀이/수학 2017. 9. 2. 14:36
    반응형

    이 글은 백준 알고리즘 문제 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


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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    private void solve() {
        StringBuilder sb = new StringBuilder();
        while(true) {
            int n = sc.nextInt();
            int m = sc.nextInt();
     
            if (n == && 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 + " ");
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.