JS Coding Blog

오른쪽에 있는 더 싼 가격 개수 세기

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

algorithm medium fenwick-tree 함수명: countSmallerPricesToRight 제한 시간: 400ms

오른쪽 구간에 자신보다 더 싼 가격이 몇 개 있는지 각 위치마다 구하는 문제입니다.

문제 설명

가격이 담긴 배열 prices가 주어집니다. 각 인덱스 i에 대해, i의 오른쪽에 있으면서 prices[i]보다 작은 값의 개수를 구해 같은 길이의 배열로 반환하는 countSmallerPricesToRight 함수를 작성하세요.

예를 들어 prices = [8, 5, 11, 4, 6, 2]라면:

  • 8의 오른쪽에는 5, 4, 6, 2가 있으므로 4
  • 5의 오른쪽에는 4, 2가 있으므로 2
  • 11의 오른쪽에는 4, 6, 2가 있으므로 3

따라서 결과는 [4, 2, 3, 1, 1, 0]입니다.

제한사항

  • 0 <= prices.length <= 100,000
  • -1,000,000,000 <= prices[i] <= 1,000,000,000
  • 반환 배열의 길이는 prices.length와 같습니다.
  • 같은 가격은 더 싼 가격으로 세지 않습니다.

예시

  • 입력: prices = [8, 5, 11, 4, 6, 2] → 출력: [4, 2, 3, 1, 1, 0]
  • 입력: prices = [3, 3, 3] → 출력: [0, 0, 0]
  • 입력: prices = [9, -1, 7, -3] → 출력: [3, 1, 1, 0]
  • 입력: prices = [] → 출력: []

힌트

  • 각 위치마다 오른쪽 전체를 다시 보면 O(n^2)가 됩니다.
  • 오른쪽에서 왼쪽으로 이동하면, 이미 본 값들은 모두 “현재 원소의 오른쪽 값들”입니다.
  • 지금까지 본 값들 중 특정 값보다 작은 원소가 몇 개인지 빠르게 구할 수 있는 자료구조를 떠올려 보세요.
  • 값의 범위가 매우 크므로, 실제 값 대신 정렬된 순위로 바꿔 다루면 편합니다.

해설

이 문제는 각 위치마다 오른쪽의 작은 원소 수를 구해야 하므로, 단순 이중 반복문으로는 O(n^2)가 되어 큰 입력에서 너무 느립니다.

핵심 아이디어는 두 가지입니다.

  1. 오른쪽에서 왼쪽으로 순회한다.
  2. 지금까지 본 값들의 빈도를 Fenwick Tree(Binary Indexed Tree)에 저장한다.

1. 왜 오른쪽에서 왼쪽으로 보나?

배열을 오른쪽에서 왼쪽으로 보면, 현재 처리하는 값보다 오른쪽에 있는 원소들은 이미 자료구조에 들어 있습니다. 즉 현재 값 prices[i]에 대해, 자료구조에는 정확히 “오른쪽 원소들”의 정보만 들어 있는 상태가 됩니다.

2. 무엇을 저장해야 하나?

현재 값보다 작은 원소 개수가 필요하므로, 값 자체를 인덱스로 쓰기보다 좌표 압축으로 각 값을 정렬 순위로 바꿉니다.

예를 들어 prices = [8, 5, 11, 4, 6, 2]이면 정렬된 서로 다른 값은 [2, 4, 5, 6, 8, 11]이고, 각 값은 다음 순위를 가집니다.

  • 2 -> 1
  • 4 -> 2
  • 5 -> 3
  • 6 -> 4
  • 8 -> 5
  • 11 -> 6

이제 Fenwick Tree에는 각 순위가 몇 번 등장했는지만 저장하면 됩니다.

3. 현재 값의 답은 어떻게 구하나?

현재 값의 압축 순위를 rank라고 하면, 현재 값보다 작은 값의 개수는 rank - 1까지의 누적 빈도 합입니다.

같은 값은 더 싼 값이 아니므로 rank까지 더하면 안 되고, 반드시 rank - 1까지만 구해야 합니다.

그 다음 현재 값 자신을 자료구조에 반영하기 위해 rank 위치의 빈도를 1 증가시킵니다.

4. 진행 예시

prices = [8, 5, 11, 4, 6, 2]

오른쪽부터 진행합니다.

  • 2: 오른쪽에 아무것도 없음 → 0, 이후 2 추가
  • 6: 오른쪽에서 6보다 작은 값은 2 → 1, 이후 6 추가
  • 4: 오른쪽에서 4보다 작은 값은 2 → 1, 이후 4 추가
  • 11: 오른쪽에서 11보다 작은 값은 4, 6, 2 → 3, 이후 11 추가
  • 5: 오른쪽에서 5보다 작은 값은 4, 2 → 2, 이후 5 추가
  • 8: 오른쪽에서 8보다 작은 값은 5, 4, 6, 2 → 4

최종 결과는 [4, 2, 3, 1, 1, 0]입니다.

5. 시간 복잡도

  • 좌표 압축용 정렬: O(n log n)
  • 각 원소마다 Fenwick Tree 질의와 갱신: O(log n)

따라서 전체 시간 복잡도는 O(n log n)이고, 추가 공간 복잡도는 O(n)입니다.

이 문제를 통해 다음 감각을 익힐 수 있습니다.

  • 오른쪽 구간 정보를 다룰 때 순회 방향을 뒤집는 발상
  • 큰 값 범위를 좌표 압축으로 다루는 방법
  • Fenwick Tree로 누적 빈도와 prefix sum을 빠르게 구하는 방법

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.