[python 파이썬] 백준 1920번 : 수 찾기

문제

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

풀이

import sys


def func(start, end):
 median = (start + end)//2
 if start >= end: return 0
 elif b > A[median]:
 return func(median+1, end)
 elif b < A[median]:
 return func(start, median)
 else: # b = A[median]
 return 1


input = sys.stdin.readline
n = int(input())
A = sorted(list(map(int, input().split())))
m = int(input())
B = list(map(int, input().split()))

for b in B:
 print(func(0,n))

처음 풀 때, 시간 생각 못하고 2중 for문 사용해서 풀었다. 

당연히 시간초과가 떴고 이진 탐색 (binary search) 를 이용해서 제 시간에 맞춰서 풀었다.

그리고 새롭게 알게 된 점은 import sys 를 하고 stdin.readline 하면 시간이 단축된다고 들어서 

계속 했었는데 큰 차이 없어보인다. 

그래서 앞으로 편하게 input 쓰려고 한다. 알고리즘이 중요한 것 같다.

먼저, A를 sort 하고

중간값을 median 이라고 했을때, 

경우의 수를 3가지로 나누었다.

1. 입력값이 median 값보다 작을때

2. 입력값이 median 값보다 클때

3. 입력값과 median 값이 같을때

이후에는 이진탐색 하는것처럼 진행하면 된다.

1 2 3 4 5

median = 3

start = 1

end = 5

입력값 = 1

--> 1<3 이므로

1 2 3

median = 2

start 1

end = 3

이런식으로 .....