[SWEA/python] 19113: 식료품 가게

문제

✔️ D3
queue

문제 흐름

N의 크기가 크지 않으므로 처음부터 순회하면서 확인하는 방식을 사용했다.

정가를 계산해 넣을 queue q와 할인가를 저장할 list result를 준비한다.
처음부터 i번째 원소를 탐색하며 만약 q의 가장 앞 원소와 일치한다면,
현재 원소는 정가이기 때문에 q에서 pop하고 넘겨준다.
만약 q가 비었거나 가장 앞 원소와 일치하지 않는다면,
현재 원소는 할인가이기 때문에 result에 추가해주고 q에 원래 가격을 계산해 삽입한다.

이 방식은 처음에 주어지는 input이 오름차순으로 정렬되어있다는 가정이 존재하기 때문에 가능한 방식이다.

코드

# 식료품 가게

import sys
from collections import deque
input = sys.stdin.readline

if __name__ == "__main__":
    t = int(input())
    for test_case in range(1, t + 1):
        n = int(input())
        prices = list(map(int, input().split()))
        
        q = deque()
        result = []
        for i in range(n * 2):
            if q and q[0] == prices[i]:
                tmp = q.popleft()
            else:
                result.append(prices[i])
                q.append(prices[i] * 4 // 3)
        print("#" + str(test_case), end=" ")
        print(*result)