[LeetCode][Kotlin] 2073. Time Needed to Buy Tickets

2073. 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 initially at position k (0-indexed) to finish buying tickets.

티켓을 구매하기 위해 줄을 서 있는 n명이 있는데, 0번째 사람이 줄 맨 앞에 있고, (n-1)번째 사람이 줄 맨 뒤에 있습니다. 

i번째 사람이 구매하려는 티켓 수는 ticket[i]인 길이 n의 0부터 인덱스된 정수 배열 티켓이 제공됩니다. 

한 사람이 티켓을 구매하는 데 정확히 1초가 걸립니다. 한 사람은 한 번에 1장의 티켓만 구매할 수 있으며 더 많은 티켓을 구매하려면 (즉시 발생하는) 줄의 끝으로 돌아가야 합니다. 구매할 티켓이 남아 있지 않으면 줄을 서게 됩니다. 

위치 k(0-인덱스)에 있는 사람이 티켓 구매를 완료하는 데 걸린 시간을 반환합니다.

 

Example 1:

Input: tickets = [2,3,2], k = 2

Output: 6

Explanation:

• The queue starts as [2,3,2], where the kth person is underlined.
• After the person at the front has bought a ticket, the queue becomes [3,2,1] at 1 second.
• Continuing this process, the queue becomes [2,1,2] at 2 seconds.
• Continuing this process, the queue becomes [1,2,1] at 3 seconds.
• Continuing this process, the queue becomes [2,1] at 4 seconds. Note: the person at the front left the queue.
• Continuing this process, the queue becomes [1,1] at 5 seconds.
• Continuing this process, the queue becomes [1] at 6 seconds. The kth person has bought all their tickets, so return 6.

Example 2:

Input: tickets = [5,1,1,1], k = 0

Output: 8

Explanation:

• The queue starts as [5,1,1,1], where the kth person is underlined.
• After the person at the front has bought a ticket, the queue becomes [1,1,1,4] at 1 second.
• Continuing this process for 3 seconds, the queue becomes [4] at 4 seconds.
• Continuing this process for 4 seconds, the queue becomes [] at 8 seconds. The kth person has bought all their tickets, so return 8.

 

Constraints:

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

---

코드 1

• 티켓을 재구매하려면 줄의 끝으로 돌아가야 한다 (Deque)
• 첫 번째 사람부터 구매하려는 티켓 수를 확인한다.
• 모든 티켓을 아직 구매하지 못했다면 줄의 끝으로 이동한다. 그리고 k 번째에 있는 사람은 앞으로 한 칸 이동한다.
• k 번째에 있는 사람의 차례가 오면 남아있는 티켓 수를 확인한다.

class Solution {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        var answer = 0
        val q = ArrayDeque(tickets.toList())
        var k = k

        while (q.isNotEmpty()) {
            var v = q.removeFirst()
            v--
            k--
            answer++

            if (v > 0) {
                q.add(v)

                if (k == -1) {
                    k = q.lastIndex
                }
            } else if (v == 0) {
                if (k == -1) {
                    return answer
                }
            }
        }

        return answer
    }
}

 

코드 2

• 규칙 1 : k 번째에 있는 사람은 앞에 있는 사람이 먼저 티켓을 구매해야 하지 구매할 수 있다.
• 규칙 2 : k 번째에 있는 사람은 뒤에 있는 사람보다 먼저 티켓을 구매할 수 있다.

class Solution {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        var answer = 0

        tickets.forEachIndexed { i, v ->
            if (i <= k) {
                answer += minOf(v, tickets[k])
            } else {
                answer += minOf(v, tickets[k] - 1)
            }
        }

        return answer
    }
}