백준 1920번 파이썬 풀이: 수 찾기

백준 1920번 수 찾기

 

알고리즘 분류: 이분탐색

 

링크: https://www.acmicpc.net/problem/1920

 

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을 출력한다.

 

문제 파악

 

문제 자체는 간단하다.

 

 n개의 정수들과 m개의 정수들이 주어지는데 m개의 정수들이 n개의 정수들 안에 있으면

 

1을 출력하고 그렇지 않으면 0을 출력하면 되는 간단한 문제이다.

 

그러나 문제가 간단한 것과 별개로 n과 m이 1부터 10만사이에서 주어지기 때문에

 

쉽게 생각하고 코드를 짜면 시간초과에 걸리기 쉽다.

 

 

코드

 

정답인 코드를 보기전에 틀린 코드부터 먼저 보자면

 

일단 많은 사람들이 시간초과로 틀린 코드는 이런식일 것이다.

 

처음에 나도 이렇게 풀고 문제가 쉽다고 생각했는데 역시나 바로 시간초과가 떴다.

 

앞서 말했듯이 n과 m이 1부터 10만 사이로 주어지기 때문에 이런식의 탐색법은

 

시간이 오래걸릴수 밖에 없다.

 

이제 정답인 코드를 보자면

 

알고리즘 분류가 이분 탐색으로 되어있는 걸 보고 이렇게 풀었다.

 

binary_search라는 함수를 만들어서 파라미터로 element, some_list, start, end가 주어진다.

 

element가 some_list라는 리스트에 들어있는지 계속 반으로 나눠가면서 확인하는 함수이다.

 

some_list의 중앙 인덱스(mid)를 찾아서 이것보다 작은곳에 위치하면 end를 mid - 1로 바꿔준다.

 

반대로 이것보다 크게되면 start를 mid + 1로 바꿔주고 우리가 찾으려는 수가 mid와 같다면

 

그대로 1을 리턴해준다.

 

만약 element가 some_list에 속해있지 않다면 binary_search함수가 진행되면서

 

element를 찾기위해 리스트가 계속 반으로 줄어들고 이 과정이 반복되다가

 

start 인덱스가 end 인덱스보다 커져버리고 이 뜻은 리스트가 반으로 나눠지면서

 

탐색을 했지만 element를 발견하지 못했다는 의미이므로 0을 리턴해준다.

 

이런식으로 재귀를 이용해서 풀어주면 계속해서 탐색범위가 반으로 줄어들기 때문에

 

시간복잡도를 줄일 수 있다고 생각했다.

 

코드를 작성하다보니 내가 만든 binary_search는 정렬된 리스트에서만 사용할수있다는걸

 

뒤늦게 깨닫고 밑에서 입력받은 n_list를 sorted를 이용해 오름차순으로 정렬해주고

 

for문을 이용해 m_list의 인덱스들이 sorted_list에 있는지 binary_search함수를 이용해 출력하였다.