[BOJ | Python] CD

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

 

문제

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

 

 

입력

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

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

 

출력

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

 

풀이

1차 시도: 테스트케이스가 여러 개라는 걸 모르고 풀어서 틀림 (0 0은 머누;;하면서 풂)

2차 시도: 1% 멈춰있다가 시간초과. 1차에서는 16%까지 풀리고 틀렸는데 이거는 1%에서 무한대기라서 당황함.

3차 시도: pypy3으로 제출 후 통과! 평소에 pypy3이랑 python3이랑 약간의 차이만 있다고 생각했는데... 큰 차이가 나서 놀랐다.

while True:
    N, M = map(int, input().split())
    
    if N == M == 0: break

    sanggeuns = [int(input()) for _ in range(N)]
    sunyeongs = [int(input()) for _ in range(N)]

    pointer1, pointer2 = 0, 0
    same_cds = 0

    while pointer1 < N and pointer2 < M:
        if sanggeuns[pointer1] == sunyeongs[pointer2]: # 상근이의 씨디와 선영이의 씨디가 똑같을 때
            same_cds += 1
            pointer1 += 1
            pointer2 += 1
        elif sanggeuns[pointer1] > sunyeongs[pointer2]: # 상근이의 씨디가 선영이의 씨디보다 더 크다면 선영이의 포인터 증가
            pointer2 += 1
        else: # pointer1 < pointer2:
            pointer1 += 1

    print(same_cds)

pointer1은 상근이의 씨디 리스트를 가리키고, pointer2는 선영이의 씨디 리스트를 가리킨다.

투포인터를 사용하면 아주 쉽게 풀리는 문제였다. (테스트케이스의 유무만 파악한다면...)