[백준][python]1756 피자굽기

문제

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

소스코드1 

if __name__ == "__main__":
    d,n = map(int,input().split())
    oven = list(map(int,input().split()))
    banjuck = list(map(int,input().split()))

    for i in range(1,d):
        oven[i] = min(oven[i-1],oven[i])
    
    cur = 0
    idx = 0
    for i in range(d-1,0,-1):
        if oven[i] < banjuck[cur]: #반죽이 더 크면 오븐에 못넣으니까 패스
            continue
        cur +=1 # 오븐에 반죽 넣으면 반죽 갯수 체크

        if cur >= n : # 주어진 반죽 모두 오븐에 넣은 경우
            idx = i+1 # i =0 부터 해서 +1 처리 해주기
            break
    print(idx)

 

소스코드2

    l = 0
    r = d-1
    for i in range(1,d):
        oven[i] = min(oven[i-1],oven[i])

    for b in banjuck: # 모든 반죽에 대해서 체크
    	idx = -1 # 반죽 체크 확인
        while l <= r:
            mid = (l+r) // 2
            if oven[mid] >= b: # 오븐이 반죽보다 크다 넣을 수는 있지만 더 작은 구간을 체크해보자 (위쪽)
                l = mid + 1
                idx = mid # 반죽 위치 체크 
            else: # 오븐이 반죽보다 작다 넣을 수도 없다 큰 구간을 체크하자
                r = mid - 1

        if idx == -1: #오븐에 반죽을 놓지 못한 경우
            break # 더이상 체크하지 않고 끝
            
        l = 0
        r = idx -1 

    print(0 if idx == -1 else idx+1)

후기

이분탐색 풀이 메모리 / 시간

 

for문 탐색 풀이 메모리 / 시간 : 시간이 훨씬 적다..