99클럽 코테 스터디 13일차 TIL + 이분탐색

오늘의 문제 - 이분탐색

백준 10815번 - 숫자 카드

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

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

---

내 풀이 및 접근 방식

1. set 이용 방식

이전에 풀었던 문제여서 코드를 봤더니 왜 set으로 n_card를 묶어줬는지 기억나지 않았다. 원래의 나라면 set으로 묶지 않았을 것 같아서 n_card를 집합화하는 코드를 삭제해서 돌려봤더니 역시나 시간 초과가 발생했다. set은 꼭 필요한 코드였다.

import sys

N = sys.stdin.readline()
N_card = list(map(int, sys.stdin.readline().split()))

M = sys.stdin.readline()
M_card = list(map(int, sys.stdin.readline().split()))

N_card = set(N_card)	# 이 코드 없으면 시간 초과

for m in M_card:
    if m in N_card:		# set 이용할 경우 O(1)이지만, 리스트 이용할 경우 O(n)
        print(1, end=' ')
    else:
        print(0, end=' ')

 

set 집합의 경우 해시 테이블을 기반으로 하므로, 특정 요소를 찾는데 걸리는 시간 복잡도는 평균적으로 O(1)이다. 이는 리스트에서 특정 요소를 찾는 데 걸리는 시간 복잡도인 O(n)과 비교했을 때 시간 효율적임을 알 수 있다.

 

시간 복잡도: O(n+m)

1. 집합 변환: O(n)
2. 검색: O(m)

2. 이분 탐색

주제가 이분 탐색이라서 이분 탐색으로도 풀어봤다. 다행히 시간 초과가 나지 않는다.

import sys

n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

n_list.sort()
answers = []
for mc in m_list:
    answer = 0
    start = 0
    end = n-1
    while start <= end:
        mid = (start+end)//2

        if n_list[mid] > mc:
            end = mid - 1
        elif n_list[mid] == mc:
            answer = 1
            break
        else:
            start = mid + 1

    answers.append(answer)

for answer in answers:
    print(answer, end=' ')

 

더 복잡해보이지만, m_card 리스트를 순회하며 각 카드 숫자와 일치하는 숫자가 n_card 리스트 중에 있는지 이분 탐색하는 것이다.

1. n_card 리스트를 정렬한다.
2. n_card 리스트의 처음 인덱스와 마지막 인덱스를 start와 end로 설정한다. answer 초기 값은 0(동일 숫자가 없는 경우)이다.
3. 인덱스를 이분하고, 인덱스에 해당하는 n 카드 숫자가 현재의 m 카드 숫자보다 크면 end를 mid-1로 설정한다. 이는 작은 범위에서의 이분 탐색을 진행하기 위함이다.
   반대로, n 카드 숫자가 현재의 m 카드 숫자보다 작다면 더 큰 범위에서의 이분 탐색을 진행하기 위해 start를 mid+1 값으로 설정한다.
   만약, n 카드 숫자가 현재의 m 카드 숫자와 같다면 answer =1로 설정하여 동일 숫자가 있는 경우로 체크하고, 이분 탐색을 종료한다.
4. 각 숫자의 이분 탐색이 종료될 때마다 answer를 answers에 추가한다.
5. answers 요소를 순서대로 출력한다.

시간 복잡도: O((n+m)logn)

1. n_list.sort() 정렬: O(nlogn) (n: n_list 길이)
2. 이진 탐색: O(mlogn) (m: m_list 길이, n: n_list 길이)
   이분 탐색의 시간 복잡도는 O(logn)이고, 이를 m 번 수행하므로 O(mlogn)이다.

 

집합을 활용한 코드가 O(n+m) 시간 복잡도를 가지므로 이분 탐색을 이용한 코드보다 더 효율적이다.

---

회고

이분 탐색을 또 써먹었다. 굳

set도 dic과 마찬가지로 해시를 특징으로 해서 탐색 시간이 O(1)임을 알았다.

탐색과 같은 문제에 자주 사용하도록 하자.