[BOJ / 백준] 10815 숫자 카드 (S5^ / 이분탐색) - Python

링크

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

 

 

 

 

문제 해석

입력

첫 번째 줄 : n
  n : 숫자 카드 개수 
두 번째 줄
  가지고 있는 숫자카드 리스트
세 번째 줄 : m
  확인할 숫자 개수 : m
네 번째 줄
  해당 숫자 카들 가지고 있는지 확인할 리스트

 

출력
해당하는 숫자 카드를 가지고 있으면 1 아니면 0으로 출력

 

 

 

 

풀이 & 코드 해석

숫자 카드가 존재하는지 완탐을 진행하면 n * m 을 진행해야하고 결국 시간초과가 발생합니다.

이분 탐색을 활용하면 시간초과를 해결할 수 있습니다.

이분 탐색은 먼저 탐색할 배열이 정렬이 되어 있어야 하고, 이를 up-down을 통해서 탐색하는 방식으로 찾고자 하는 방법을 찾을 수 있습니다.

 

 

 

코드

n = int(input())

arr = list(map(int, input().split()))

m = int(input())

check_list = list(map(int, input().split()))

# sort
arr.sort()

# up-down 진행
for now in check_list:
    s = 0
    e = n - 1
    ans = 0

    while s <= e:
        mid = (s + e) // 2

        if now > arr[mid]:
            s = mid + 1
        elif now == arr[mid]:
            ans = 1
            break
        else:
            e = mid - 1

    print(ans, end=" ")

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java