[백준 | 파이썬3] 1920: 수찾기- 이진탐색

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

1920번: 수 찾기

> 이진탐색 활용

 

#1. 런타임 에러

처음에는 target number가 있는 리스트들에 대한 반복문을 돌리면서 타겟이 A리스트에 있으면 if target in A:  1을 출력하고 아니면 0을 출력하도록 했다. 하지만 역시 런타임 에러가 났다.

1초당 1억번의 연산을 할 수 있다고 하면 n과 m에 최대 100,000개의 정수가 들어가기 때문에 최악의 경우 10억번 이상의 연산이 필요하기 때문이다. 시간 제한이 2초니 당연히 런타임 에러가 난다. 

 

 

 

#2. 이진탐색 활용

따라서 O(logN)의 시간복잡도를 가지는 이진탐색을 활용해야 런타임 에러가 발생하지 않는다. 

 

데이터 입력

함수 선언 및 결과 출력

 

> 다른 사람의 풀이

처음 #1에서 생각한 아이디어를 런타임 에러가 안나도록 구현할 수 있는 코드이다. 시간도 1/3배로 줄일 수 있다.

open으로 시스템에서 직접 입력을 받아 타겟 넘버가 A리스트에 있는지 확인하고, 있으면 True값을 1로 없으면 False값을 0으로 출력하도록 했다.