회전한 점수판 구간 합 빠르게 구하기
자바스크립트 코딩테스트 문제로 circular-prefix-sum 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
점수판 scores가 원형으로 놓여 있습니다.
각 질의 [rotation, left, right]는 점수판을 오른쪽으로 rotation칸 회전했을 때, 보이는 배열의 left번 인덱스부터 right번 인덱스까지의 합을 구하라는 뜻입니다.
모든 질의의 답을 순서대로 담은 배열을 반환하는 rotatingScoreRangeSums 함수를 작성하세요.
제한사항
1 <= scores.length <= 100000-10000 <= scores[i] <= 100001 <= queries.length <= 100000- 각 질의는
[rotation, left, right]형태입니다. 0 <= rotation <= 10000000000 <= left <= right < scores.length- 반환값은 각 질의의 구간 합을 순서대로 담은 배열입니다.
예시
- 입력:
scores = [10, 20, 30, 40, 50],queries = [[1, 0, 1], [2, 1, 3], [0, 2, 4]]→ 출력:[60, 80, 120] - 입력:
scores = [5, -2, 7, 1],queries = [[3, 0, 2], [1, 2, 3], [8, 1, 1]]→ 출력:[6, 5, -2] - 입력:
scores = [42],queries = [[100, 0, 0], [0, 0, 0]]→ 출력:[42, 42]
힌트
- 오른쪽으로
r칸 회전한 뒤 보이는 인덱스i는 원본 배열의(i - r + n) % n위치와 대응됩니다. - 원형 구간 합은 배열을 두 번 이어 붙인 뒤 누적합을 만들면 끊김 없이 계산할 수 있습니다.
rotation은scores.length로 나눈 나머지만 실제 배치에 영향을 줍니다.
해설
질의마다 실제로 배열을 회전하면 한 번의 질의에 최대 O(n)이 걸려 전체 시간이 커집니다.
회전은 인덱스 대응만 바꾸므로 배열 자체를 움직일 필요가 없습니다.
배열 길이를 n, 오른쪽 회전 수를 r % n이라고 합시다.
회전된 배열의 left 위치는 원본 배열의 (left - r + n) % n 위치에서 시작합니다.
left부터 right까지의 길이는 right - left + 1입니다.
원본 배열을 두 번 이어 붙인 배열의 누적합을 만들어 두면, 시작 위치에서 길이만큼 이어지는 원형 구간 합을 한 번의 뺄셈으로 구할 수 있습니다.
따라서 전처리는 O(n), 각 질의는 O(1)에 처리할 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.