[알고리즘] 백준 10815 파이썬 - 숫자 카드

 

10815번: 숫자 카드

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

문제풀이

import sys
input = sys.stdin.readline
N=int(input())
List=list(map(int,input().split()))
#이분 탐색을 위해 정렬
List.sort()
M=int(input())
List2=list(map(int,input().split()))
#출력할 리스트를 List2 크기만큼 만듦
List3 = [0]*len(List2)

#이분 탐색 시작
for i in range(len(List2)):
    first=0
    last=N-1
    while first<=last:
        mid=(first+last)//2
        #가장 먼저 중간값이랑 같은지 확인
        if(List2[i]==List[mid]):
            List3[i]+=1
            break
        #크다면 first 값에 1을 더해 mid값을 크게 만듦
        elif(List2[i]>List[mid]):
            first=mid+1
        #작다면 last 값에 1을 빼 mid값을 작게 만듦
        else:
            last=mid-1
#완성된 리스트를 공백 단위로 한 줄에 모두 출력
print(*List3)

- 이분 탐색이라는 개념을 사용하여서 문제를 풀었다.

  이진 탐색이라고 불리우는데, 즉 가운데 값이랑 비교하여 찾는 값이 작은지 큰지를 확인한다.

  결과적으로 찾는 영역을 줄여 코드의 과부하를 줄인다.

 

 (이진 탐색의 더 자세한 내용은 아래 링크를 참조)

이진 탐색