[백준/Python] 4158번: CD

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

4158번: CD

---

---

문제 분석

상근이와 선영이가 가지고 있는 CD의 수는 각각 N, M개이며 이는 최대 1,000,000(백만)이다.

처음엔 상근이가 가지고 있는 CD와 선영이가 가지고 있는 CD를 set 자료구조를 활용하여 교집합을 구하면 풀릴 것이라고 생각하였지만 입력 범위가 커 시간 초과가 났다.

 

풀이 방법은 다양하겠지만 3개의 풀이 방법을 설명하려고 한다.

 

---

 

1. set 자료구조를 활용하여 in을 통한 개수 확인

먼저 들어오는 상근이가 가지고 있는 CD를 set을 통해 미리 저장해두고 선영이가 가지고 있는 CD가 입력될 때마다 상근이가 가지고 있는지 확인 후 개수 누적

 

코드

import sys

input = sys.stdin.readline

while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    sang = set()
    for _ in range(n):
        sang.add(int(input()))

    cnt = 0
    for _ in range(m):
        sun = int(input())

        if sun in sang:
            cnt += 1

    print(cnt)

---

2. 이분 탐색을 이용한 개수 확인

문제에서 이미 CD 번호가 오름차순이기 때문에 따로 정렬이 필요하지 않다.

이분 탐색을 이용한다면 '무엇을 탐색해야 하는지'가 가장 중요하다.

이분 탐색을 통해 확인해야 할 것은 선영이가 가지고 있는 CD가 상근이도 가지고 있는지 확인해야 하며 이는 index를 이분 탐색해 확인할 수 있다.

 

코드

import sys

input = sys.stdin.readline

while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    sang = []
    for _ in range(n):
        sang.append(int(input()))

    cnt = 0
    for _ in range(m):
        sun = int(input())
        # 상근이의 list에서 처음과 끝의 index를 판단
        start, end = 0, n - 1

        # start가 end보다 커지면 종료
        while start <= end:
            mid = (start + end) // 2

            # 상근이에게 선영이가 가지고 있는 CD가 있다면
            if sang[mid] == sun:
                # 개수를 추가하고 break
                cnt += 1
                break
            # 만약 상근이의 인덱스 mid 값이 선영이의 CD 값보다 크다면 탐색 구간을 앞으로
            elif sang[mid] > sun:
                end = mid - 1
            # 상근이의 인덱스 mid 값이 선영이의 CD 값보다 작다면 탐색 구간을 뒤로
            else:
                start = mid + 1

    print(cnt)

이분 탐색을 이용하여 시간을 줄였지만 list 자료구조를 사용하였기 때문에 탐색 속도가 굉장히 느려 Python 3에서는 시간 초과, PyPy 3에서만 통과가 되는 코드이다.

---

3. 두 포인터를 활용한 개수 확인

문제에서 이미 CD 번호가 오름차순이기 때문에 따로 정렬이 필요하지 않다.

상근이와 선영이가 가진 CD를 모두 list에 담아둔 후 각각의 탐색 인덱스를 pointer1, pointer2로 설정하여

하나씩 이동하면서 탐색 후 일치하면 개수를 누적한다.

이 때 하나의 배열이 마지막까지 탐색을 마쳤다면 더 탐색할 필요가 없기 때문에 종료된다.

 

코드

import sys

input = sys.stdin.readline

while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    sang = []
    for _ in range(n):
        sang.append(int(input()))

    sun = []
    for _ in range(m):
        sun.append(int(input()))
	
    # 상근이와 선영이를 탐색할 인덱스 값
    pointer1, pointer2 = 0, 0
    cnt = 0
	
    while pointer1 < n and pointer2 < m:
    	# 상근이의 값보다 선영이의 값이 더 크다면 상근이의 인덱스를 늘려줌
        if sang[pointer1] < sun[pointer2]:
            pointer1 += 1
        # 선영이의 값이 상근이의 값보다 더 크다면 선영이의 인덱스를 늘려줌
        elif sang[pointer1] > sun[pointer2]:
            pointer2 += 1
        # 만약 두 값이 일치한다면 개수를 늘리고 모두 인덱스를 늘려줌
        else:
            cnt += 1
            pointer1 += 1
            pointer2 += 1

    print(cnt)

---

 

하나의 문제를 다양한 방법으로 풀어보는 습관을 길러 생각하는 폭을 넓히는 연습을 하면 좋을 것 같다.

이분 탐색의 경우는 탐색해야 하는 것이 무엇인지 파악하는 것이 가장 중요하고 어려운 일인 것 같다.