Python 백준 2751 set in과 list in 비교 + 이진탐색 풀이

문제

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

10815번: 숫자 카드

시간 제한이 2초인 문제이다. 따라서 기본적인 로직을 생각하고, 시간복잡도를 고려했어야 했다. 문제를  list를 이용하는 경우 혹은 순차탐색을 이용할 경우 시간초과로 문제를 풀 수 없었다. 

- 첫 풀이 

import sys
N = int(input())
n_lst = sys.stdin.readline().strip().split()

M = int(input())
m_lst = sys.stdin.readline().strip().split()
for i in range(M):
    if m_lst[i] in n_lst:
        m_lst[i] = 1
    else:
        m_lst[i] = 0
for i in range(M):
    print(m_lst[i], end=" ")

이 때 2가지 접근법이 존재하는데 이를 각각 확인해보자 

풀이1 set 이용하기 

간단하게 x in n부분을 x in set으로 바꾸어준다.

즉, n_lst를 set으로 바꾸면 해결된다

import sys
N = int(input())
n_set = set(sys.stdin.readline().strip().split())

M = int(input())
m_lst = sys.stdin.readline().strip().split()
for i in range(M):
    if m_lst[i] in n_set:
        m_lst[i] = 1
    else:
        m_lst[i] = 0
for i in range(M):
    print(m_lst[i], end=" ")

set의 시간복잡도(O(1)) vs list의 시간복잡도(O(n))

위의 방식으로 풀면 왜 해결될까?? 

그 이유는 python에서 set은 내부적으로 해시테이블로 구현되어있기 때문이다.

-해시 테이블

자료구조 중 하나로 해시를 이용해서 해싱을 한 값을 인덱스로 사용하는 자료형 

-해시 함수

임의의 크기의 데이터를 받아 일정한 크기의 데이터로 반환하는(해시) 함수 

해시 테이블의 예를 들면 아래 그림과 같다. 

즉, 리스트에서는 어떤 값이 있는지 확인하려면 값을 일일이 확인하기 때문에 x in s 연산이 O(n)이 된다, 

반면 해시테이블로 구현된 세트의 경우 인덱스로 접근함으로써, 해당 값이 있는지 거의 바로 확인 가능하기에 O(1)의 시간 복잡도를 가진다(collison이 일어나는 경우는 제외하자) 

풀이2 이진탐색(Binary search) 이용하기 

순차탐색을 하게 되면 시간초과가 나는 경우가 많다. 그렇기에 이런 경우 binary search를 통해 시간복잡도를 줄여줄 수 있다. 

재귀를 이용해 이진탐색을 구현하면 다음과 같다.

이때 return을 잘 해주자(왼쪽, 오른쪽 탐색 시 return을 안하면 값을 반환하지 않는다)

import sys

N = int(input())
n_lst = list(map(int, sys.stdin.readline().split()))
M = int(input())
m_lst = list(map(int, sys.stdin.readline().split()))

n_lst.sort() #binary search need sorted array

def binary_search(data, target, start, end):
    if start > end:
        return None

    mid = (start+end)//2

    if target == data[mid]:
        return data[mid]
    elif data[mid] > target:
        #왼쪽 탐색
        return binary_search(data, target, start, mid-1)
    elif data[mid] < target:
        #오른쪽 탐색
        return binary_search(data,target,mid+1,end)
    else:
        return None


for i in range(M):
    if binary_search(n_lst, m_lst[i], 0, N - 1) != None:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

참고

https://velog.io/@ready2start/Python-%EC%84%B8%ED%8A%B8set%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] 세트(set)의 시간 복잡도