[이분탐색] [백준] 실5 숫자카드 + [프로그래머스] LV3 입국심사

문제1

 

내가 가진 카드 더미와

찾아야할 카드 숫자들

 

방법 1

이분탐색을 위해 내가 가진 카드더미를 정렬 시키고 이분탐색 구현하면

import sys

N = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))



cards.sort()


for check in checks:
    exist=False
    left,right=0, len(cards)-1
    while left<=right:
        temp=(left+right)//2
        # print(check,"idx",temp,cards[temp])
        if cards[temp] < check:
            left=temp+1
        elif cards[temp]>check:
            right=temp-1
        else:
            # print("찾음",cards[temp],check)
            exist=True
            break
    print("1" if exist else "0", end=" ")

 

 

방법 2

딕셔너리 key값으로 내가 가진 숫자카드 저장해두었다가 if findKey in myDic: 하는게 훨씬 빠름

import sys

N = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))


myDic={}
for i in range(N):
    myDic[cards[i]]=0

for j in range(M):
    if checks[j] in myDic:
        print("1", end=' ')
    else:
        print("0", end=' ')

 

 

 

문제2

주석 잘 읽기

def solution(n, times):
    answer = 0
    
    left=1
    right=max(times)*n #가장 오래걸리는 사람이 모든 사람을 검사할 때 소요 시간
    
    while left<=right:
        temp=(left+right)//2
        people=sum(temp // time for time in times) #심사관 한명당 temp분(시간)동안 몇명 검사할 수 있는지 확인 후 모두 더하면 최종 검사가능한 사람 수
        
        if people<n :
            left=temp+1
        elif people>=n: #n과 people이 같아도 최소시간 아닐수 있으니까 저장해두고 right줄여서 재탐색
            answer=temp #현재가 최소시간일 수 있으므로 저장
            right=temp-1

   
    
    return answer