[Python] 백준_1920_수 찾기(시간 초과 해결)

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

 

 

첫 풀이(시간 초과)

import sys
input = sys.stdin.readline

N = int(input())
n_num = list(map(int,input().split()))
M = int(input())
m_num = list(map(int, input().split()))

for j in m_num:
    if j in n_num:
        print(1)
    else:
        print(0)

N의 리스트를 돌면서 M의 값을 찾는 것은 너무 쉬운 일이 아닐까라고 자만했지만, 바로 시간초과가 나왔습니다.

역시 세상에 쉬운일이란 없습니다. 늘 그렇듯 쉬운길을 찾으려 import sys도 넣었지만 택도 없었어요.

 

풀이 1 (이분탐색 이용)

def binarySearch(arr,l,h, key):
    if l > h:
        return 0
        
    else:
        mid = (l+h) // 2 # 중간 인덱스 값
        
        mid_num = arr[mid] # 중간 숫자
        
        if key == arr[mid]: #찾는값이랑 중간 값이랑 같으면
            return 1
            
        elif key < mid_num: # 키 값이 작으면
            return binarySearch(arr, l, mid-1, key)
            
        elif key > mid_num: # 키 값이 크면
            return binarySearch(arr, mid + 1, h, key)
            
        else:
            return 0

N = int(input())

n_num = list(map(int,input().split()))

M = int(input())

m_num = list(map(int, input().split()))


n_num.sort()


for j in m_num:

    print(binarySearch(n_num, 0, N - 1, j))

드디어 시간을 줄일 수 있는 방법을 알아냈습니다. 바로 이분탐색입니다.

이분탐색에서는 중요한 조건이 있습니다. 바로 리스트가 정렬되어 있어야 한다는 것입니다.

처음에는 이것을 놓쳐 오랜 시간 헤메었으니 다음에는 이분 탐색과 정렬을 반드시 기억할 것입니다.

 

풀이2 (set이용)

N = int(input())

N_set = set(map(int, input().split()))

M = int(input())

M_lst = list(map(int, input().split()))

for i in M_lst:

    if i in N_set:
    
        print(1)
        
    else:
    
        print(0)

훨씬 더 간단한 방법을 들고왔습니다. 처음 N개의 정수를 리스트로 받았다면, set으로 받는 것입니다.

 

어떤 차이가 발생하는 것일까요? 문제에서 우리는 찾는 숫자가 n에 있는 지 없는 지만 찾고 있습니다.

 

리스트 같은 경우에는 처음부터 끝까지 다 돌면서 확인을 하기에 if i in n_num의 시간 복잡도는 O(n)입니다.

하지만 set은 순서가 없기 때문에 존재 여부만 판단할 때의 시간 복잡도는 O(1)입니다. 굉장히 시간이 빨라졌죠.

 

이렇게 시간초과를 두 가지 방법으로 해결해보았습니다. 더 많이 공부하고 익혀야겠습니다. 알고리즘 화이팅.