백준 1920

링크

백준 1920

수 찾기

처음풀땐 무대뽀로 풀었다. 결과는 시간초과..
어떻게 해야하나 고민하다가 결국 검색해봤다. 이진탐색 알고리즘을 활용해서 푸는 문제였다.
이진탐색 알고리즘을 보다보니 학교에서 수업을 들었던게 생각났다. 머리속에서 남김없이 사라진줄만 알았는데 어딘가에 꼭꼭 숨겨놨었다.
이진탐색 알고리즘의 핵심은 절반씩 줄여나가며 탐색하는데 있다.
리스트를 절반씩 줄여나가므로 탐색해야할 리스트의 길이가 2**(1/2) 씩 줄어든다. 따라서 O(logN)의 시간복잡도를 갖는다.

• 이진탐색 알고리즘

  • 탐색할 리스트를 오름차순으로 정렬한다 반드시 오름차순! 매우중요
  • start 지점과 end 지점을 만든다. 인덱스를 사용하므로 start=0, end=리스트의길이-1
  • 리스트의 가운데 지점인 middle ((start+end)//2) 과 찾는 숫자를 비교한다.
    
  • 만약 찾는 숫자가 middle보다 작을경우 end를 가운데 지점으로 옮기고 middle을 다시계산한다.
    옮기는이유 : 어차피 찾는 숫자가 가운데 지점보다는 작기때문에 기존 middle보다 큰값들은 생각하지 않아도 된다.
    
  • 만약 찾는 숫자가 가운데 지점보다 클 경우 start를 가운데 지점으로 옮겨준다.
    옮기는이유 : 어차피 찾는 숫자가 가운데 지점보다는 크기때문에 기존 middle보다 작은값들은 생각하지 않아도 된다.
    
    
  • middle과 찾는 숫자가 같아질때까지 반복한다.
  • start가 end보다 커지면 반복을 종료한다. (리스트에 찾는 숫자가 존재하지 않음)

오답 1

# 시간초과
 import sys

 N = input()
 arr_n = list(map(int, sys.stdin.readline().split()))
 M = input()
 arr_m = list(map(int, sys.stdin.readline().split()))

 for m in arr_m:
     if m in arr_n:
         print(1)
     else:
         print(0)

이진탐색에 대해 공부한 후 다시 코드를 작성했다.

정답 코드

import sys

N = input()
arr_n = list(map(int, sys.stdin.readline().split()))
arr_n.sort()
M = input()
arr_m = list(map(int, sys.stdin.readline().split()))

def bs(arr, number): #탐색할 리스트와 숫자를 받아옴
    s = 0
    e = len(arr) - 1 #start와 end 초기화
    while s <= e:
        mid = (s + e) // 2
        if arr[mid] == number: #middle과 숫자가 같으면 종료
            return True
        elif arr[mid] > number: #middle보다 숫자가 작으면
            e = mid -1 #end를 기존 mid의 -1로 할당 (mid와 이미 비교했으니까)
        else: #middle보다 숫자가 크면
            s = mid +1 #start를 기존 mid의 +1로 할당
    return False #start가 end보다 커져서 반복이 끝난다면 찾는 숫자가 리스트에 존재하지 않음

for m in arr_m:
    if bs(arr_n, m) == False:
        print(0)
    else:
        print(1)

알게된 것👨‍💻

• 이진탐색알고리즘