[python] 백준 1158번 오답노트

deque 문제를 풀 때 리스트를 먼저 만들어서 틀렸었는데,
지난 주의 코테에서도 같은 실수를 범해서 문제를 풀지 못했다..ㅠㅠ
지금이라도 소 잃고 외양간 고치는 심정으로 비슷한 문제들을 찾아서 풀어본다.
백준 1158번

1. circ 덱이 빌 때까지 반복한다.

circ.append(circ.popleft())

2. k-1번 동안 덱의 왼쪽에서 오른쪽으로 사람들을 이동시킨다.
3. k번째 사람을 덱에서 제거하고, 제거된 사람을 ans 리스트에 추가한다.

import sys
input = sys.stdin.readline
from collections import deque
n, k = map(int, input().split())

circ = deque()
for i in range(1, n+1):
    circ.append(i)
ans = []

while circ:
    for i in range(k-1):
        circ.append(circ.popleft())
    ans.append(circ.popleft())

print(str(ans).replace('[','<').replace(']','>'))

백준 25096번
[문제]
deque의 모든 팬케이크를 손님에게 줘야한다.
손님들은 한 번에 한 명씩 도착하며, 각 손님은 한 개의 팬케이크를 받습니다.
각 손님에게 왼쪽 끝이나 오른쪽 끝의 팬케이크 중 하나를 제공해야 한다.
팬케이크가 제공되면, 그 팬케이크는 deque에서 사라진다.

팬케이크가 하나만 남았을 때는 그 팬케이크를 제공해야 한다.

각 팬케이크는 맛 점수를 가지고 있다.
손님들은 자신이 받은 팬케이크가 이전 손님들이 받은 모든 팬케이크보다 맛 점수가 같거나 높을 때에만 팬케이크에 대한 비용을 지불한다. (첫 번째 손님은 이전 손님이 없기 때문에 항상 비용을 지불한다.)

팬케이크를 제공하는 순서를 최적화하여 비용을 지불하는 손님의 수를 최대화할 때,
얼마나 많은 손님이 팬케이크에 대한 비용을 지불하게 될까

예제입력

4
2
1 5
4
1 4 2 3
5
10 10 10 10 10
4
7 1 3 1000000

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
이후 각 테스트 케이스마다 두 줄이 주어진다.
첫 줄에는 팬케이크의 수 𝑁이 주어진다. 두 번째 줄에는 𝑁개의 정수가 주어지고 차례로 왼쪽에서부터 맛점수이다.

예제출력

Case #1: 2
Case #2: 3
Case #3: 5
Case #4: 2

예제 설명
Case #1:
팬케이크의 맛 점수: [1, 5]
첫 번째 손님은 1을 받고 비용 지불
두 번째 손님은 5를 받고 비용 지불
총 2명의 손님이 비용 지불

Case #2:
팬케이크의 맛 점수는 [1, 4, 2, 3]
첫 번째 손님은 1을 받고 비용 지불
두 번째 손님은 4를 받고 비용 지불
세 번째 손님은 3을 받고 비용 지불X
네 번째 손님은 2를 받고 비용 지불
총 3명의 손님이 비용 지불

Case #3:
팬케이크의 맛 점수는 [10, 10, 10, 10, 10]
모든 손님이 각각 10을 받고 비용 지불
총 5명의 손님이 비용을 지불

Case #4:
팬케이크의 맛 점수는 [7, 1, 3, 1000000]
첫 번째 손님은 7을 받고 비용 지불
두 번째 손님은 1000000을 받고 비용 지불
총 2명의 손님이 비용 지불

t = int(input().strip())
test_cases = []

for _ in range(t):
    n = int(input().strip())
    pancakes = list(map(int, input().strip().split()))
    test_cases.append((n, pancakes))

t는 테스트 케이스의 수
각 테스트 케이스마다 n과 팬케이크의 맛 점수 리스트를 입력받아 test_cases에 추가

def max_paying_customers(T, test_cases):
    results = []
    for case_number in range(1, T + 1):
        N, pancakes = test_cases[case_number - 1]
        dq = deque(pancakes)
        
        max_deliciousness = -1
        paying_customers = 0
        
        while dq:
            if dq[0] <= dq[-1]:
                pancake = dq.popleft()
            else:
                pancake = dq.pop()
            
            if pancake >= max_deliciousness:
                paying_customers += 1
                max_deliciousness = pancake
        
        results.append(f"Case #{case_number}: {paying_customers}")
    
    return results

각 테스트 케이스마다 덱을 사용
팬케이크를 왼쪽 또는 오른쪽에서 하나씩 제공하면서, 제공된 팬케이크의 맛 점수가 이전에 제공된 팬케이크 중 가장 높은 맛 점수보다 높은 경우에만 손님이 비용을 지불
최적화된 순서로 팬케이크를 제공하여 최대한 많은 손님이 비용을 지불