배지 추첨 순서 복원하기

자바스크립트 코딩테스트 문제로 order-statistics 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium order-statistics 함수명: reconstructBadgeOrder 제한 시간: 400ms

문제 설명

번호가 1부터 n까지 붙은 배지가 오름차순으로 놓여 있습니다.

배지를 하나씩 뽑아 새 줄을 만들 때, 배열 pickRanks의 i번째 값은 그 순간 아직 남아 있는 배지들 중 0부터 세었을 때 몇 번째로 작은 배지를 뽑는지를 뜻합니다.

모든 선택이 끝났을 때 만들어지는 배지 번호 순서를 반환하는 reconstructBadgeOrder 함수를 작성하세요.

예를 들어 pickRanks = [2, 0, 1, 0]이면 처음에는 [1, 2, 3, 4] 중 0-based 2번째인 3을 뽑습니다. 이후 남은 배지는 [1, 2, 4]이고, 0번째인 1을 뽑습니다. 최종 결과는 [3, 1, 4, 2]입니다.

제한사항

0 <= pickRanks.length <= 100000
n = pickRanks.length입니다.
각 단계 i에서 0 <= pickRanks[i] < n - i를 만족하는 입력만 주어집니다.
반환값은 선택된 배지 번호를 순서대로 담은 배열입니다.
단순히 배열에서 splice로 제거하는 풀이는 큰 입력에서 느릴 수 있습니다.

예시

입력: pickRanks = [2, 0, 1, 0] -> 출력: [3, 1, 4, 2]
입력: pickRanks = [0, 0, 0] -> 출력: [1, 2, 3]
입력: pickRanks = [3, 2, 1, 0] -> 출력: [4, 3, 2, 1]
입력: pickRanks = [1, 1, 1, 0] -> 출력: [2, 3, 4, 1]

힌트

남아 있는 배지는 1, 제거된 배지는 0으로 생각해 보세요.
“남아 있는 배지 중 k번째”를 빠르게 찾으려면 누적 개수를 기준으로 이분 탐색할 수 있습니다.
Fenwick Tree를 쓰면 특정 번호가 남아 있는지 갱신하고, 앞쪽에 남은 배지가 몇 개인지 빠르게 계산할 수 있습니다.

해설

매번 남아 있는 배지 배열에서 pickRanks[i]번째 원소를 직접 꺼내고 삭제하면, 중간 원소 삭제 때문에 최악의 경우 O(n^2) 시간이 걸립니다.

배지 번호 1..n을 모두 남아 있는 상태로 보고 Fenwick Tree에 각 위치의 값을 1로 저장합니다. 어떤 배지를 뽑으면 해당 번호 위치를 0으로 갱신합니다.

이제 pickRanks[i]가 r일 때 실제로 필요한 것은 남아 있는 배지 중 r + 1번째 번호입니다. Fenwick Tree의 누적합은 특정 번호 이하에 남아 있는 배지 개수를 뜻하므로, 누적합이 처음으로 r + 1 이상이 되는 가장 작은 번호를 찾으면 됩니다.

그 번호를 정답 배열에 넣고 Fenwick Tree에서 -1로 갱신하면 다음 단계의 순위 기준이 자동으로 줄어듭니다.

각 단계마다 Fenwick Tree 탐색과 갱신을 O(log n)에 수행하므로 전체 시간 복잡도는 O(n log n), 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과