[파이썬] 백준 1756번 피자 굽기

백준 #1756 피자 굽기

• 백준 1756번 피자 굽기 문제풀기

# 제멋대로인 오븐에 피자 반죽을 넣는다

# 출력: 가장 마지막 피자 반죽의 깊이

# 이전에 들어간 피자보다 이번에 들어갈 피자가 작거나 같다면
    # 단순히 한 층 쌓는 격이다.
    # 1, 2, 3, 4 이런 식으로 쌓으면 불리함
# 어떤 피자보다 작은 오븐의 층을 구해서 쌓는다.
    # 300000, 299999, 299998 이런 식으로 쌓으면 불리함
# 두 방법을 혼용해본다.

# 1. 오븐 각각의 지름이 가장 먼저 나타나는 층을 저장한다.
# 2-1. 피자 반죽의 지름이 d라면 그보다 오븐 지름이 작은 층 중에
    # 가장 위에있는 층을 구해서 그 위에 쌓는다.
    # 구한 층이 현재 층보다 아래 있다면 단순히 한 층 쌓는다.
# 2-2. 피자 반죽이 이전 반죽보다 작거나 같으면 단순히 한 층 쌓는다.
# 3. 가장 마지막 피자 반죽의 깊이를 구한다.

def solution(D, N):
    oven = list(map(int, input().split()))
    where = dict()

    for i in range(len(oven)):
        if not where.get(oven[i]):
            where[oven[i]] = i+1
    
    pizza = list(map(int, input().split()))
    before = pizza[0]
    keys = sorted(list(where.keys()))
    idx = 0

    if before == 1: D -= 1
    else:
        floor = float('inf')
        for i in range(len(keys)):
            if keys[i] >= before: 
                idx = i
                break
            floor = min(floor, where.get(keys[i]))
        if floor != float('inf'): D = floor - 2
        else: D -= 1
    
    for i in range(1, len(pizza)):
        if D <= 0: 
            print(0)
            break
        if pizza[i] <= before:
            D -= 1
            continue
        floor = float('inf')
        for j in range(idx, len(keys)):
            if keys[j] >= pizza[i]:
                idx = j
                before = pizza[i]
                break
            floor = min(floor, where.get(keys[j]))
        if floor != float('inf') and floor <= D: D = floor - 2
        else: D -= 1
    else:
        print(D+1)

if __name__ == '__main__':
    solution(*map(int, input().split()))