2차원 행렬이 하나 주어져 있고, 각 행에는 두 개의 값 [키, 카운트]가 담겨 있습니다. 여기서 '키'는 해당 사람의 신장을 의미하고, '카운트'는 그 사람 앞에 서 있는 사람들 중 자신과 키가 같거나 더 큰 사람의 수를 뜻합니다. 이 대기열이 무작위로 섞여 있다고 가정할 때, 원래의 줄 서기 순서를 복원해야 합니다.
문제 예시
예를 들어 입력이 다음과 같다면,
| 2 | 2 |
| 4 | 0 |
| 5 | 0 |
출력은 다음과 같습니다.
| 4 | 0 |
| 5 | 0 |
| 2 | 2 |
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- N := 행렬의 행 개수
- 행렬의 행들을 키 오름차순, 같은 키라면 카운트 내림차순으로 정렬
- ans := 크기가 N인 리스트를 만들고, 모든 요소를 None으로 초기화
- 정렬된 행렬의 각 행에 대해 키 h와 카운트 c를 순회하며:
- temp := 0
- ans 리스트의 각 인덱스 i와 값 num에 대해:
- temp >= c 이고 num이 None이라면 → ans[i] := [h, c]를 저장한 뒤 반복문 탈출
- num이 None이거나 num[0] >= h라면 → temp를 1 증가
- ans 반환
동작 원리: 키가 작은 사람부터 차례로 배치하면, 이미 배치된 사람들 중 현재 사람보다 크거나 같은 키의 수만 세면 됩니다. 아직 채워지지 않은 빈자리(None)에는 나중에 더 큰 키의 사람이 들어갈 수 있으므로, 빈자리도 함께 계산에 포함하는 것이 이 알고리즘의 핵심입니다.
파이썬 구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
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]]