[백준 4158번] [C언어] CD

 

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

4158번: CD

 

난이도 : 실버 5
태그 : 자료 구조, 이분 탐색, 해시를 사용한 집합과 맵, 두 포인터

 

 

설명

두 사람이 공통으로 갖고 있는 CD의 개수를 출력하는 문제입니다.

이중 for문을 사용하여 같은 CD를 체크할 경우 시간초과에 걸릴게 뻔하므로, 다른 풀이를 생각해보아야 합니다.

 

1 3 6 7 9와 1 2 3 5 9, 두 개의 배열이 있습니다.

양쪽의 배열 index를 가르킬 ptr1, ptr2가 있고, 각각 0부터 출발합니다.

 

ptr1, ptr2가 가르키는 값은 1로 같습니다.

이 경우, ptr1, ptr2 모두 증가시켜줍니다

 

 

ptr1이 가르키는 값은 3, ptr2가 가르키는 값은 2 입니다.

두 배열은 오름차순 정렬되어 있기 때문에,

ptr1이 가르키는 값 이후의 값들은 모두 ptr2보다 큽니다.

따라서 작은쪽인 ptr2를 증가시킵니다.

 

ptr1, ptr2가 가르키는 값이 서로 같습니다. 이 경우 양쪽 포인터 둘 다 증가시켜줍니다.

 

ptr1이 가르키는 원소는 6, ptr2가 가르키는 원소는 5입니다.

이 경우, ptr1의 원소 6 이후의 값인 7, 9는 모두 5보다 큽니다.

작은쪽인 ptr2를 증가시킵니다.

ptr1은 6, ptr2는 9로,

작은쪽인  ptr1을 증가시킵니다.

마찬가지로, 작은쪽인 ptr1을 증가시킵니다.

 

ptr1, ptr2가 가르키는 값이 같습니다.

더 이상 탐색할 원소가 없으므로 탐색을 종료합니다.

찾은 공통원소는 1, 3, 9로 3개 입니다.

 

소스코드

#include <stdio.h>
#include <stdlib.h>

int main() {
    while (1) {
        int n, m, ptr1, ptr2;
        scanf("%d %d", &n, &m);

        if (n == 0 && m == 0) break;

        int* arr1 = (int*)malloc(n * sizeof(int));
        int* arr2 = (int*)malloc(m * sizeof(int));

        for (int i = 0; i < n; i++) {
            scanf("%d", &arr1[i]);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &arr2[i]);
        }

        ptr1 = ptr2 = 0;
        int cnt = 0;

        // 양쪽 ptr이 배열을 넘지 않을때까지 반복
        while (ptr1 < n && ptr2 < m) {
            // ptr1보다 ptr2이 크면 ptr1을 +1
            if (arr1[ptr1] < arr2[ptr2]) {
                ptr1++;
            }
            // ptr1이 ptr2보다 크면 ptr2를 +1
            else if (arr1[ptr1] > arr2[ptr2]) {
                ptr2++;
            }
            // 양쪽 ptr이 같으면 공통원소 카운트를 하고, 양쪽 ptr을 +1
            else {
                cnt++;
                ptr1++;
                ptr2++;
            }
        }
        printf("%d\n", cnt);
    }
}

 

위의 접근방식을 코드로 나타내었습니다.

 

주의하실 점은 입력은 여러개의 테스트 케이스로 주어져있고,

0, 0이 나올때까지 반복한다는 점입니다.

즉, n과 m이 주어지는 상황이 여러개라는 것입니다.

 

문제의 예제 입력에는 나와있지 않지만, 아래와 같은 입력이 주어질 수도 있다는 것이죠.

여러개의 테스트 케이스가 주어진다는 점에 유의하셔야 합니다.

3 3
1
2
3
1
2
4
3 3
1
2
3
1
2
4
3 3
1
2
3
1
2
4
0 0

 

 

후기

잘 풀었다고 생각했는데... 왜 안되지? 하던 중,

입력이 여러개의 테스트케이스임을 알고 당황했던 문제였습니다.

마지막에 입력으로 0, 0을 왜 주나 했네요.