[Silver V] CD - 4158

문제 링크

성능 요약

메모리: 222252 KB, 시간: 1780 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 두 포인터

문제 설명

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

입력

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

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

출력

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

---

풀이

아이디어

단순히 이분탐색 문제로 인식하였고, 문제에서 오름차순으로 주어진다고 하였으므로, 정렬은 따로 필요하지 않습니다.
따라서 이분탐색의 시간복잡도인 $O(\log N)$의 시간복잡도를 가지게 된다.

이때 주의해야 할 점은 이분탐색의 탐색범위를 지정하는것에 신경을 써야 한다.
아무 생각없이 1씩 늘렸다가 TLE가 발생했고, 한참 찾느라 고생했다.

두번째로 실수한 부분은 마지막에 0 0이 주어진다고 하였는데, 둘다 0이 들어올 때 까지 프로그램이 종료되서는 안된다.
따라서 무한루프를 이용하여 조건 검사를 해주고, 조건이 만족할 때까지 반복을 돌려주었다.

파이썬에서 시간초과를 막기 위해 sys 모듈을 Import 하여 사용하였다.

코드

import sys
input = sys.stdin.readline
print = sys.stdout.write
def bi_search(lst, start, end, target): # start와 end는 인덱스
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] == target:
            return 1
        elif lst[mid] < target:
            start  = mid + 1
        else:

            end = mid - 1
    return 0

while True:
    n, m = map(int, input().split())
    n_list = []
    m_list = []
    if n == 0 and m == 0:
        break

    for _ in range(n):
        n_list.append(int(input()))

    for _ in range(m):
        m_list.append(int(input()))

    result = 0
    for x in n_list:
        start, end = 0, len(m_list)
        result += bi_search(m_list, start, end, x)
    print(str(result)+"\n")

아래 코드는 이분탐색을 사용한 코드이며, 파이썬의 set을 사용하면 조금 더 빠르게 찾을 수 있고, 코드 또한 간결해진다.

set에서의 탐색의 시간복잡도는 $O(1)$로 훨씬 빨라지는 것을 알 수 있다.
아래는 set을 이용한 풀이이다.

import sys
input = sys.stdin.readline
# print = sys.stdout.write

while True:
    n, m = map(int, input().split())
    n_list = []
    m_list = []
    if n == 0 and m == 0:
        break

    for _ in range(n):
        n_list.append(int(input()))

    for _ in range(m):
        m_list.append(int(input()))

    print(len(set(n_list) & set(m_list)))

---

회고

간단한 문제라고 만만하게 푼것이 다양한 실수의 원인이었다.
또한 집합을 사용하는 간단한 방법을 생각하지 못하고 "이분탐색" 이라는 틀에 박혀있었다. 항상 느끼는 거지만 문제를 풀때는 틀을 깨고 봐야 한다.