BOJ 1920 : 수 찾기 (Python)

문제

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

1920번: 수 찾기

 

 

코드

from bisect import bisect_left, bisect_right

n = int(input())
nlist = list(map(int, input().split()))
nlist.sort()
m = int(input())
mlist = list(map(int, input().split()))

for i in range(m):
    if (bisect_right(nlist, mlist[i])-bisect_left(nlist, mlist[i])):
        print(1)
    else:
        print("result= "+str(bisect_right(nlist,
              mlist[i])-bisect_left(nlist, mlist[i])))
        print(0)

 

풀이

• 정렬된 list 에서 이진탐색을 이용함
• bisect_left(list, num)
  -> list 내에서 num 이 들어갈 수 있는 가장 왼쪽의 index를 반환
• bisect_right(list, num)
  -> list 내에서 num 이 들어갈 수 있는 가장 오른쪽의 index를 반환
  
  
  ex) [1,2,2,4,5] 리스트에서 2라는 숫자가 들어갈 수 있는 가장 왼쪽 index는 1, 가장 오른쪽 index는 3
  
  
• num이 list에 존재한다면 삽입할 같은 숫자의 num은 list에 존재하는 num의 앞뒤로 모두 들어갈 수 있을 것이므로 bisect_left(list,num)-bisect_right(list,num) 은 1 이상일 것
• 반대로 num이 list에 존재하지 않는다면 어느 숫자들 사이에 한군데만 들어갈 수 있으므로 bisect_left(list,num)-bisect_right(list,num) 은 0일 것

---

참고사항

if num in list:

이런 식으로 list 내에서 num 을 찾으려고 하면 시간초과가 뜸.