[2024] day 101. Leetcode 2073. Time Needed to Buy Tickets

gunny·2024년 4월 10일

Leetcode 2073. Time Needed to Buy Tickets Leetcode 2073. Time Needed to Buy Tickets python

코딩테스트

목록 보기

414/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 9일 (화)
Leetcode daily problem

2073. Time Needed to Buy Tickets

https://leetcode.com/problems/time-needed-to-buy-tickets/?envType=daily-question&envId=2024-04-09

Problem

n명의 사람들이 티켓을 사기 위해 줄을 서고 있을 때, k번째에 해당하는 사람이 티켓을 사기 위해 필요한 시간을 반환한다.
이 때, 티켓을 사기 위한 룰은 한 턴에 1개씩만 구매할 수 있고 k번째 해당하는 사람이 사야하는 티켓의 수를 소모하기 위해서는 다시 줄의 맨 끝으로 가서 티켓을 구매해야 한다.

예를 들어 example 1에서 주어진 tickes = [2,3,2] 는 총 3명의 사람이 티켓을 사기 위해 줄을 서있는 것이고 1번째 사람은 2개의 티켓, 2번째 사람은 3개의 티켓, 3번째 사람은 2개의 티켓을 구매하는 것이다.

k =2 일때, 배열의 인덱스는 0부터 시작해서 k=2는 세 번째 사람을 의미하고 3 번째 사람은 티켓 2개를 구매하기 위해서 앞의 두명의 티켓을 구매하는 2초와, 자신의 티켓을 구매할 때의 1초가 소요되고, tickets = [1,2,1] 이 된다. 마지막 한개의 티켓을 사기 위해서 또 다시 앞의 두명의 티켓을 구매하는 2초가 소모되고 마지막 하나를 구매하기 위한 1초가 소모되어 총 6초가 필요하다.
그리고 tickets = [0,1,0] 이 된다.

Solution

queue

티켓을 사기 위해 사람들이 한 줄로 서서 하나의 턴에 1개의 티켓을 구매할 수 있으므로, 큐를 사용해서 티켓을 구매해야 하는 사람들을 줄 선 순차적으로 큐에 넣는다. 그리고 제일 먼저 들어간 원소(사람) 부터 차례대로 빼낸다.
이때 빼내는 과정에서 1초씩 소모되므로 time을 +1 하면서 업데이트 해나간다.
그러는 과정에서 구매해야 하는 티켓을 소모시킨다. 이때 티켓을 소모시키는 과정에서 해당 원소(사람)이 k와 같고 가지고 있는 티켓이 0이 되면 업데이트했던 시간을 반환하고, 0이 아니면 다시 큐에 넣는 과정을 반복한다.

Code

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        queue = deque()
        time = 0
        
        for i in range(len(tickets)):
            queue.append(i)
            
        while queue:
            time +=1
            front = queue.popleft()
            tickets[front] -= 1
            
            if front==k and tickets[front]==0:
                return time
            if tickets[front] != 0:
                queue.append(front)
                
        return time