[BOJ][#] 1920 | 수 찾기

1920 | 수 찾기
https://www.acmicpc.net/problem/1920

 

 

 

작성 코드

 

import sys

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

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

for M_num in M_nums:
    if M_num in nums:
        print('1')
    else:
        print('0')

 

• 시간 초과

 

이상 코드

 

set 사용

 

import sys

N = int(sys.stdin.readline())
nums = set(map(int, sys.stdin.readline().split()))

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

for M_num in M_nums:
    if M_num in nums:
        print('1')
    else:
        print('0')

 

• list 대신 set을 사용함으로써 시간 복잡도 줄임

 

 

이분 탐색 사용

 

import sys

n = sys.stdin.readline()
N = sorted(map(int, sys.stdin.readline().split()))

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

def binary(num, N, start, end):

    if start > end:
        return 0

    mid = (start + end) // 2

    if num == N[mid]:
        return 1
    elif num < N[mid]:
        end = mid - 1
    else:
        start = mid + 1
    
    return binary(num, N, start, end)
    
for num in M:
    start = 0
    end = len(N)-1
    answer = binary(num, N, start, end)
    print(answer)

 

 

 

학습

 

• 집합 자료형에서 containment, 즉 요소를 찾는 것은 list와 달리 시간복잡도가 O(1) / remove, discard 연산도 마찬가지로 O(1)

 

• 탐색과 확인이 주로 필요한 연산 -> Set이나 Dictionary
• 순서와 index에 따른 접근이 필요 -> List
  
  
• 이분 탐색 (binary search) -> 중간 값을 비교하여 이전 이후 탐색으로 나눔
• 시간 복잡도 O(log n)
• 재귀 함수말고도 반복문을 사용하는 방법 있음