[BOJ] 4158번 CD - C++

문제 보러가기: https://www.acmicpc.net/problem/4158

---

문제

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

입력

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

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

출력

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

 

---

문제 접근

 본 문제의 제한 시간은 '1초'로 약 1억 번 이하의 연산 횟수로 문제를 해결할 수 있어야 합니다. 입력으로 주어지는 N과 M은 최대 100만이라고 하였습니다.

  만약 상근이와 선영이가 공통으로 가지고 있는 CD의 개수를 2중 for문으로 풀게 된다면 1,000,000 * 1,000,000은 1조가 되어버립니다. 이를 위하여 우리는 O(N * M)의 시간 복잡도를 two pointer 알고리즘을 통하여 O(N + M)로 줄일 필요가 있습니다. 이 경우에는 최대로 잡는다 해도 2,000,000번의 연산이 전부일 것입니다(물론, 문제 자체에서 0 0이 입력될 때까지 반복을 하고 있기 때문에 반복 횟수를 N이라고 한다면 2,000,000N번의 연산을 할 것입니다).

 

풀이 코드

#include <iostream>
using namespace std;

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


    while (1) {
        int n, m;
        cin >> n >> m;

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

        int arr1[n];
        int arr2[m];

        for (int i = 0; i < n; i++) cin >> arr1[i];
        for (int i = 0; i < m; i++) cin >> arr2[i];
        
        int i = 0;
        int j = 0;

        int answer = 0;

        while (i < n && j < m) {
            if (arr1[i] == arr2[j]) {
                i++; j++;
                answer++;
            } else {
                if (arr1[i] < arr2[j]) {
                    i++;
                } else { // arr1[i] > arr2[j]
                    j++;
                }
            }
        }
        cout << answer << '\n';
    }

}