가까운 구간 안의 비슷한 가격 알림
자바스크립트 코딩테스트 문제로 bucketization 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
가게 가격 기록 배열에서, 서로 너무 멀지 않은 두 시점의 가격이 거의 같은 순간이 있는지 찾는 문제입니다.
문제 설명
정수 배열 prices, 정수 windowSize, 정수 limit가 주어집니다.
서로 다른 두 인덱스 i, j가 아래 두 조건을 모두 만족하면 비슷한 가격 알림이 발생한다고 정의합니다.
|i - j| <= windowSize|prices[i] - prices[j]| <= limit
조건을 만족하는 쌍이 하나라도 있으면 true, 없으면 false를 반환하는 hasNearbySimilarPrice 함수를 작성하세요.
제한사항
1 <= prices.length <= 100,000-1,000,000,000 <= prices[i] <= 1,000,000,0000 <= windowSize <= 100,0000 <= limit <= 1,000,000,000- 반환값은 불리언 값입니다.
예시
- 입력:
prices = [10, 13, 11, 20],windowSize = 2,limit = 2→ 출력:true - 입력:
prices = [5, 14, 30, 5],windowSize = 2,limit = 0→ 출력:false - 입력:
prices = [7, 7],windowSize = 0,limit = 0→ 출력:false
첫 번째 예시에서는 인덱스 0의 값 10과 인덱스 2의 값 11이 인덱스 차이 2, 값 차이 1이라 조건을 만족합니다.
힌트
- 모든 쌍을 비교하면
O(n^2)라 길이가 큰 입력에서 너무 느립니다. - 인덱스 차이 제한이 있으므로, 현재 위치 기준으로 최근
windowSize개 원소만 관리하면 됩니다. - 값 차이 제한은 숫자 범위를 일정한 크기 구간으로 나누면 더 빠르게 검사할 수 있습니다.
해설
핵심은 두 조건을 따로 보는 것입니다.
- 인덱스 차이 제한
- 현재 인덱스를
i라고 하면,i - windowSize보다 앞에 있는 원소는 더 이상 후보가 아닙니다. - 따라서 최근
windowSize개 원소만 유지하는 슬라이딩 윈도우로 생각할 수 있습니다.
- 현재 인덱스를
- 값 차이 제한
- 값 차이가
limit이하인 두 수는 길이가limit + 1인 버킷으로 나눴을 때, 같은 버킷에 있거나 바로 이웃한 버킷에만 들어갈 수 있습니다. - 예를 들어
limit = 2면 버킷 크기는 3입니다. - 같은 버킷에 두 수가 들어가면 그 차이는 자동으로 2 이하입니다.
- 값 차이가
풀이 흐름은 다음과 같습니다.
- 버킷 크기를
limit + 1로 둡니다. - 현재 값이 들어갈 버킷 번호를 계산합니다.
- 같은 버킷에 값이 이미 있으면 바로
true입니다. - 왼쪽 인접 버킷, 오른쪽 인접 버킷의 값과도 실제 차이가
limit이하인지 확인합니다. - 현재 값을 버킷에 넣습니다.
- 윈도우 크기를 넘긴 가장 오래된 값은 자기 버킷에서 제거합니다.
버킷 번호를 계산할 때 음수 값도 있으므로 단순 정수 나눗셈 대신 Math.floor(value / bucketSize)처럼 바닥 나눗셈 기준으로 처리해야 안전합니다.
각 원소는 버킷에 한 번 들어가고 한 번 빠지므로 전체 시간 복잡도는 O(n)이고, 추가 공간은 윈도우에 비례해 O(windowSize)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.