파이썬에서 섞인 사람들의 대기열을 복구하는 프로그램

각 행에 2개의 값 [height, count]이 포함된 2D 행렬이 있다고 가정해 보겠습니다. 이 값은 사람이 키를 주었다는 것을 나타내고 그들 앞에 최소한 그들만큼 키가 큰 사람의 'count' 수가 있습니다. 이제 이 대기열이 셔플되었다고 생각하면 대기열의 원래 순서를 복구해야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• N :=행렬의 행 수
• 높이 증가 및 개수 감소에 따라 행렬 행 재정렬
• ans :=크기가 N인 목록을 만들고 처음에는 모든 항목이 null입니다.
• 각 높이 h에 대해 행렬 행에서 c를 계산합니다. do
  • 온도 :=0
  • 각 인덱스 i와 값 num에 대해 do
    • temp> =c이고 num이 null이면
      • ans[i] :=[h, c]
      • 루프에서 나오다
    • num이 null이거나 num[0]>=h이면
      • temp :=온도 + 1
• 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

class Solution:
   def solve(self, matrix):
      N = len(matrix)
      matrix.sort(key=lambda x: [x[0], -x[1]])
      ans = [None] * N

      for h, c in matrix:
         temp = 0
         for i, num in enumerate(ans):
            if temp >= c and num is None:
               ans[i] = [h, c]
               break

            if num is None or num[0] >= h:
               temp += 1
      return ans

ob = Solution()
matrix = [
   [2, 2],
   [4, 0],
   [5, 0]
]
print(ob.solve(matrix))

입력

[[2, 2],[4, 0],[5, 0]]

출력

[[4, 0], [5, 0], [2, 2]]