백준 1920번 - 수 찾기 [58]

---

문제 유형 : 정렬, 이분탐색

---

문제

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

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

---

제한사항

• 입력

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

• 출력

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

---

• x in a : 시간 복잡도 O(n)

  x 값이 list a에 있는지 확인하는 연산 입니다. x가 있는지확인하기 위해 리스트 a를 전체 탐색 해야 하므로 시간의 복잡도가 n 입니다.

  출처: https://hyun-am-coding.tistory.com/entry/Python-list-연산에-따른-시간-복잡도 [현암 코딩]

  => **따라서 in말고 다른 방법을 사용해야한다. **

  시간초과가 난 코드

  n = int(input())
  aList = list(map(int,input().split(" ")))
  m = int(input())
  presentList = list(map(int,input().split(" ")))
  for x in presentList:
      if x in aList:
          print(1)
      else:
          print(0)
  

• 이분탐색을 이용

  • start = mid+1, end= mid end를 이렇게 해야하는 이유가 뭘까
  • index를 사용한거라서 그런가?

---

solution

n = int(input())
aList = list(map(int,input().split(" ")))
m = int(input())
presentList = list(map(int,input().split(" ")))
aList.sort()
def binary(arr,x):
    start = 0
    end = len(arr)
    while start < end:
        mid = (start + end) //2
        if arr[mid] == x:
            return True
        elif arr[mid] > x:
            end = mid
        else:
            start = mid +1
    return False

for x in presentList:
    print("1" if binary(aList,x) else "0")

나의 한마디

이건 좀 헷갈린다… 나중에 한번 더 봐야지