[LeetCode] 2073. Time Needed to Buy Tickets

문제 바로가기

https://leetcode.com/problems/time-needed-to-buy-tickets/

 

💡 문제

There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

ex)

Input	Output	Explanation
tickets = [2,3,2], k = 2	6	- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
		- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
		The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.
tickets = [5,1,1,1], k = 0	8	- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
		- In the next 4 passes, only the person in position 0 is buying tickets.
		The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

 

💡 내 코드

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        count=0
        while tickets[k]!=0:
            for i in range(len(tickets)):
                if tickets[k]==0:
                    break
                if tickets[i]==0:
                    continue
                
                tickets[i]-=1
                count+=1
        
        return count

Runtime: 51 ms, faster than 35.04% of Python3 online submissions
Memory Usage: 16.6 MB, less than 51.83% of Python3 online submissions

💡 내 코드의 시간복잡도

O(n*m)

 

💡 다른 풀이

• 현재 사람이 k번째 이전 혹은 k번째인 경우, 0부터 k번째 사람이 필요로 하는 티켓 갯수 중 최솟값 만큼 티켓을 가지게 된다.

  ex) 0 … 현재 … k번째 일 때, 다음과 같다.

  현재 사람이 필요한 갯수	k번째 사람이 필요한 갯수	현재 사람이 얻을 수 있는 갯수
  2	4	2
  4	3	3

  • 첫 번째 예시: 현재 사람이 필요로 하는 갯수인 2개를 다 받으면(tickets[current]=0이 되면), 현재 사람이 필요로 하는 갯수가 0이 되기 때문에 현재 사람은 더이상 받을 수 없음.
  • 두 번째 예시: k번째 사람이 필요로 하는 갯수인 3개를 다 받으면(tickets[k]=0이 되면), k번째 사람이 필요로 하는 갯수가 0이 되기 때문에 더이상 티켓을 배부하지 않아도 됨.

• 현재 사람이 k번째 이후인 경우, k번째 이후의 사람들은 k번째 사람이 필요로 하는 갯수에 비해 티켓을 얻을 수 있는 기회가 적다. (왜냐하면, k번째 사람이 필요로 하는 갯수를 모두 얻을 경우 티켓 배부가 끝나기 때문.)

  → k번째 이후의 사람이 얻을 수 있는 티켓 갯수 = 0 ~ (tickets[k]-1)

  • k번째 이후의 사람이 필요로 하는 갯수 < k번째 사람이 필요로 하는 갯수:
    • k번째 이후의 사람이 필요로 하는 갯수 만큼 얻을 수 있음.
  • k번째 이후의 사람이 필요로 하는 갯수 ≥ k번째 사람이 필요로 하는 갯수:
    • k번째 사람이 필요로 하는 갯수 - 1 만큼 얻을 수 있음.

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
         count= 0
        
        for i in range(len(tickets)):
            if i <= k:
                count += min(tickets[i], tickets[k])
            else:
                count += min(tickets[k]-1, tickets[i])
        
        return count

Runtime: 34 ms, faster than 94.18% of Python3 online submissions
Memory Usage: 16.5 MB, less than 92.60% of Python3 online submissions

이렇게 할 경우, 시간 복잡도는 O(n)이 된다.