백준 4158 : CD (Python)

본문 링크

import sys
input=sys.stdin.readline


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

    if N==0 and M==0:
        exit(0)

    N_list=[] ; M_list=[]

    for i in range(N):
        N_list.append(int(input()))

    for i in range(M):
        M_list.append(int(input()))

    index_N=0 ; index_M=0 ; total=0

    while index_N<N and index_M<M:

        if N_list[index_N]==M_list[index_M]:
            total+=1
            index_N+=1 ; index_M+=1

        elif N_list[index_N]>M_list[index_M]:
            index_M+=1
        else:
            index_N+=1

    print(total)   

📌 어떻게 문제에 접근할 것인가?

문제는 간단하다. 상근이와 선영이가 가지고 있는 공통된 CD 의 개수를 구하는 문제이다.
다만 문제에서 주어지는 $N,M$ 의 범위는 $1≤N,M ≤1,000,000$ 이다.
즉 $O(N^2)$ 으로 완전탐색을 하면 시간초과가 난다.
따라서 모든 리스트를 $O(N)$ 으로 탐색가능한 투 포인터를 사용하기로 한다.

📌 어떻게 투 포인터를 사용할 것인가?

먼저 상근이와 선영이의 리스트를 정렬해준다. 그리고 움직이는 포인터 2개를 N_list 에서 움직이는 포인터 , M_list 에서 움직이는 포인터를 만들어 준다.
이후 매번 두 값을 비교해 같은지 확인한다. 같으면 total+=1 을 하고 N_list 와 M_list 의 인덱스를 동시에 움직인다.
N_list 값이 더 크다면 그보다 더 적은 M_list 의 인덱스 값을 증가시킨다.
반대로 M_list 값이 더 크다면 N_list 의 인덱스 값을 증가시킨다.

✅ 코드에서 주의해야할 부분

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 따라서 while 문을 사용한다.
• 상근이와 선영이의 CD가 같을때 포인터를 동시에 움직인다.