합이 나누어떨어지게 만드는 가장 짧은 제거 구간

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

algorithm medium prefix-modulo 함수명: shortestRemovalForDivisibleSum 제한 시간: 500ms

문제 설명

정수 배열 nums와 양의 정수 p가 주어집니다. nums에서 연속된 구간을 최대 한 번 제거해 남은 원소들의 합이 p로 나누어떨어지게 만들려고 합니다.

제거할 수 있는 구간의 최소 길이를 반환하세요. 이미 전체 합이 p로 나누어떨어진다면 0을 반환합니다. 단, 배열 전체를 제거하는 것은 허용하지 않으며, 불가능하면 -1을 반환합니다.

제한사항

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000000
2 <= p <= 1000000000
제거 구간은 연속된 원소들로 이루어져야 합니다.
남은 배열은 비어 있으면 안 됩니다.

예시

입력: nums = [3, 1, 4, 2], p = 6 → 출력: 1
입력: nums = [6, 3, 5, 2], p = 9 → 출력: 2
입력: nums = [1, 2, 3], p = 3 → 출력: 0
입력: nums = [1, 2, 3], p = 7 → 출력: -1

힌트

전체 합의 나머지가 r이라면, 제거하는 구간의 합도 p로 나눈 나머지가 r이어야 합니다.
누적합의 나머지를 저장해 두면, 현재 위치에서 끝나는 제거 후보 구간을 빠르게 찾을 수 있습니다.

해설

전체 합을 p로 나눈 나머지를 need라고 하겠습니다. need가 0이면 아무 구간도 제거하지 않아도 되므로 답은 0입니다.

그 외에는 합의 나머지가 need인 가장 짧은 연속 구간을 찾아야 합니다. 왼쪽부터 누적합의 나머지 prefix를 계산하면서, 이전 누적합 중 (prefix - need + p) % p와 같은 나머지가 있었는지 확인합니다. 그런 이전 위치가 있다면 그 다음 칸부터 현재 위치까지의 구간 합은 need와 같은 나머지를 가집니다.

각 나머지에 대해 가장 최근 인덱스를 저장하면 같은 나머리가 여러 번 나와도 더 짧은 구간을 만들 수 있습니다. 마지막에 찾은 최소 길이가 배열 전체 길이와 같거나 후보가 없다면 배열 전체를 제거해야 하는 경우이므로 -1을 반환합니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과