[백준] 10815번 숫자 카드

사용 언어 - Python3

문제 -  10815번 숫자 카드

이분탐색 : 업다운 게임. 절반부터 시작해서 효과적으로 범위를 줄인다. 

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

10815번: 숫자 카드

 

정답

이분탐색 - 절반부터 값과 같은지, 큰지, 작은지 확인 후 포인터 수정

s = 0, e = n-1, mid = (s+e)//2

 

1. 정렬 시키기

이분탐색은 기준 숫자카드가 정렬되어 있어야 중간값보다 크고/작다 대소비교가 가능하다.

 

2. flag = False

flag 가 True라면 1 print / False 라면 0 print

  

3. while s <= e 교차되지 않았다면 계속 반복해준다.

중간값 == num) flag = True, break 끝

중간값 > num) up 중간값이 너무 컸다. = 끝포인터를 중간값으로 둔다. 이때 중간값이 답이 아닌 것은 확정이기 때문에 굳이 또 포함시킬 필요는 없다. e = mid-1

중간값 < num) down 중간값이 너무 작았다. = 시작포인터를 중간값으로 둔다. 이때 중간값이 아닌 것은 확정이기 때문에 굳이 또 포함시킬 필요는 없다. s = mid+1

 

import sys
input = sys.stdin.readline

n = int(input()) # 숫자카드 개수
arr_n = sorted(list(map(int,input().split()))) # 숫자카드
m = int(input()) # 구해야할 정수
arr_m = list(map(int,input().split()))

for num in arr_m:
    s = 0
    e = n-1
    flag = False
    
    while s <= e: # 교차되지 않았다면
        mid = (s+e)//2
        if arr_n[mid] == num : # answer
            flag = True
            break
        elif arr_n[mid] > num : # up
            e = mid-1            
        else: # down
            s = mid+1
    if flag:
        print(1, end = ' ')
    else:
        print(0, end = ' ')

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/10815_%EC%88%AB%EC%9E%90%EC%B9%B4%EB%93%9C.py