백준 알고리즘 10815 [파이썬]

알고리즘

백준 알고리즘 10815 [파이썬]

Brad Daeho Lee 2021. 3. 13. 00:13

배운 내용

이 문제는 시간초과 때문에 이분탐색을 사용해야한다.

이분탐색은 리스트안에서 내가 원하는 값이 있는지 탐색할 때 첫번 째 index와 마지막 index 사이에 중간 index를 찾아서 그 중간 값이 원하는 값이면 탐색이 거기서 끝나고 만약 중간값보다 작으면 찾는 값이 중간 값을 기준으로 왼쪽에서 찾아보면 된다. 그리고 만약에 찾는 값이 중간값보다 크면 중간 값을 기준으로 그 오른쪽에서 찾아보면 된다.

또 하나 더 배운것은 만약 lst = [10, 20, 30, 40] 이 리스트 값을 10 20 30 40 이라는 형태로 출력하기 위해서

" ".join(map(str, lst)) = 10 20 30 40

사용하면 된다. join() int에 사용할 수 없기 때문에 string으로 바꿔줬다.

문제

문제풀이

N = int(input())
num_N = list(map(int, input().split()))
# 이분탐색을 위해서 num리스트를 정렬.
num_N.sort()
M = int(input())
num_M = list(map(int, input().split()))
lst = []
for i in range(M):
  left= 0 #num_N 처음숫자 index
  right = N-1 #num_N 마지막숫자
  lst.append(0)
  while left <= right:
    mid = (left+right)//2
    if num_N[mid] == num_M[i]:
      lst.pop()
      lst.append(1)
      break
    elif num_N[mid] > num_M[i]:
      right = mid-1
    else:
      left = mid+1
answer = " ".join(map(str, lst))
print(answer)

오늘부터 문제풀이 영상을 찍어서 올리기로 했습니다.

손으로 푸는것과 입으로 설명하는건 다르다고했기에 나중에 남에게 나의 코드를 설명하기위해서 좋은 연습이 될것같습니다!