1942. The Number of the Smallest Unoccupied Chair

Problem :

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:31:51

 

---

 

문제 설명

 

 

0부터 n-1번까지의 숫자가 매겨진 n명의 친구들의 파티가 있다. 이 파티에는 0부터 무한대까지 숫자가 매겨진 무한대의 의자가 있다. 만약 한 친구가 파티에 도착한다면, 그들은 가장 적은 숫자의 점유되지 않은 의자에 앉는다.

 

* 예를 들어, 한 친구가 왔을 때 0, 1, 5 의자가 점유되었다면 그 친구는 2번 의자에 앉을 것이다.

 

친구가 파티를 떠날때, 그 친구가 떠나는 순간에 그 친구의 의자는 점유되지 않은 상태가 된다. 만약 다른 친구가 동시에 도착한다면, 그들은 그 의자에 앉을 수 있다.

 

2차원의 0-인덱스 times 배열과 정수 targetFriend을 입력으로 받는다. 이 때 times[i] = [arrivali, leavingi]로, i번째 친구가 도착하고 떠난 시간을 의미한다. 모든 도착 시간은 개별적이다(단 하나임이 보장된다)

 

targetfriend 번째의 친구가 도착했을 때 앉을 의자 번호를 반환하라.

---

 

풀이

 

우선순위 큐를 사용해 보자.

targetFriend가 들어오는 시점에 제일 적은 숫자의 의자를 구해야하며, 모든 의자에 앉고 일어서는 행위는 현재 남아있는 의자 중 제일 적은 숫자의 의자에 의존한다. 즉 이런 작업에는 우선순위 큐를 적용해볼 만하다.

 

• 좌석은 무한하지만, 친구는 최대 n명이다. n개 좌석만을 사용하는 빈 좌석 우선순위 큐를 준비한다.
• 새로운 친구 i가 들어왔을 때
  • 우선순위 큐에서 index를 pop한다.
  • 해당 자리를 기록해 둔다.
• 의자에 앉은 친구 i가 떠날때
  • 친구 i가 앉은 index를 구한다.
  • index에 해당하는 자리를 다시 우선순위 큐에 넣어 준다.

풀이 코드

class Solution:
    def sit(self) :
        idx = heapq.heappop(self.emptyQueue)
        return idx

    def unsit(self, idx) :
        heapq.heappush(self.emptyQueue, idx)

    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        friend = len(times)
        self.emptyQueue = list(range(friend))
        heapq.heapify(self.emptyQueue)
        self.loc = [-1]*friend

        rank = [(i, j) for i in range(friend) for j in range(2)]
        rank.sort(key = lambda x: (times[x[0]][x[1]], -x[1]))
        
        for f, s in rank :
            if s == 0 :
                self.loc[f] = self.sit()
            else :
                self.unsit(self.loc[f])
            if (f, s) == (targetFriend, 0) :
                return self.loc[f]
        return 0