[Queue] Queue Reconstruction by Height

2차원 배열로 이루어져있는 데이터의 각 원소는 [height, number]로 구성되어 있다.

이때 number는 특정 원소보다 앞에 있는 원소의 height가 같거나 높은 원소의 갯수를 말한다.

예를들어 [ [1,0], [2,0], [1,2] ] 이라는 배열이 있다면, 세번째 원소는 height가 1이고, 그 앞에(in front) 1보다 크거나 같은 원소가 두개 있으므로 number가 2가 된다.

order가 무작위로 들어오는 이 이차원 배열을 순서대로 reconstruct하라는 것이 문제이다.

 

그저 데이터를 queue로 관리하기만 하면 되는 간단한 문제다.

일단 height에 대해 내림차순으로 정렬한 후, 같은 숫자에 대해서는 number에 대해 내림차순으로 정렬한다.

 

이 문제가 greedy인 이유는 최종 정렬로직 때문이다.

내림차순으로 정렬된 2차원배열에 대해 Loop를 돌며, number의 조건에 따라 splice로 알맞은 위치에 끼워넣는다

(참고로 splice( a,b,c)는 a원소부터 b개를 지우고 c로 대체한다)

 

예시의 [ 5, 0 ]은 해당원소 앞에 아무런 원소가 없으므로, 결과 배열의 0번째 위치에 끼워넣는다.

[4, 4]의 경우는 해당원소앞에 4개의 원소가 있다는 뜻이므로 4번째 위치에 끼워넣어준다.

이렇게 Loop를 돌며 각 원소를 해당시점까지의 global과 비교하여 연산하므로 일종의 greed algorithm이 된다.