누적 피로도가 나누어떨어지는 근무 구간 수
자바스크립트 코딩테스트 문제로 prefix-remainder-count 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
하루 동안의 피로도 변화량 배열 fatigueChanges와 양의 정수 k가 주어집니다.
연속한 근무 구간을 하나 골랐을 때, 그 구간의 피로도 변화량 합이 k로 나누어떨어지면 “정산 가능한 구간”이라고 합니다. 정산 가능한 연속 구간의 개수를 반환하는 countDivisibleWorkSegments 함수를 작성하세요.
제한사항
1 <= fatigueChanges.length <= 100000-10000 <= fatigueChanges[i] <= 100001 <= k <= 10000- 정답은 JavaScript의 안전한 정수 범위 안에 들어옵니다.
- 연속 구간은 최소 1개 이상의 원소를 포함해야 합니다.
예시
- 입력:
fatigueChanges = [4, 5, 0, -2, -3, 1],k = 5-> 출력:7 - 입력:
fatigueChanges = [1, 2, 3],k = 3-> 출력:3 - 입력:
fatigueChanges = [-1, 2, 9],k = 5-> 출력:1 - 입력:
fatigueChanges = [0, 0, 0],k = 4-> 출력:6
힌트
- 어떤 두 누적합을
k로 나눈 나머지가 같다면, 두 지점 사이의 구간 합은k의 배수입니다. - 지금까지 나온 나머지별 개수를 저장해 두면, 현재 나머지와 같은 이전 지점의 개수만큼 새 구간을 만들 수 있습니다.
- JavaScript에서
-1 % 5는-1이므로 나머지를((value % k) + k) % k처럼 보정하는 것이 안전합니다.
해설
연속 구간의 합을 매번 직접 구하면 구간의 수가 많아져 O(n^2)이 됩니다. 대신 누적합의 나머지를 이용하면 배열을 한 번만 순회하며 정답을 구할 수 있습니다.
인덱스 i까지의 누적합을 prefix[i]라고 하면, l부터 r까지의 구간 합은 prefix[r] - prefix[l - 1]입니다. 이 값이 k로 나누어떨어지려면 두 누적합의 나머지가 같아야 합니다.
따라서 현재까지 등장한 누적합 나머지의 개수를 Map에 저장합니다. 새 원소를 더해 현재 나머지를 구했을 때, 같은 나머지가 이전에 m번 나왔다면 현재 위치에서 끝나는 정산 가능한 구간도 m개 생깁니다. 그 뒤 현재 나머지의 등장 횟수를 1 늘립니다.
처음에는 아무 원소도 더하지 않은 누적합 0이 이미 한 번 존재한다고 보고 나머지 0의 개수를 1로 둡니다. 그래야 배열의 시작점부터 현재 위치까지의 합이 바로 k로 나누어떨어지는 경우도 자연스럽게 셀 수 있습니다.
피로도 변화량에는 음수가 포함될 수 있으므로 나머지 계산 후에는 반드시 0 이상 k - 1 이하로 보정해야 합니다. 전체 배열을 한 번 순회하므로 시간 복잡도는 O(n), 저장하는 나머지는 최대 k개이므로 공간 복잡도는 O(k)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.