세 구간 합이 모두 같은지 확인하기
자바스크립트 코딩테스트 문제로 partition-scan 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배열을 세 개의 연속 구간으로 나눴을 때 각 구간의 합이 모두 같은지 확인하는 문제입니다.
문제 설명
정수 배열 nums가 주어집니다.
이 배열을 비어 있지 않은 세 개의 연속 구간으로 나눌 수 있는지 확인하세요.
세 구간의 합이 모두 같으면 true, 아니면 false를 반환하는 checkEqualThreePartSum 함수를 작성하세요.
구간은 반드시 원래 순서를 유지해야 하며, 각 원소는 정확히 하나의 구간에만 포함되어야 합니다.
제한사항
nums의 길이는3이상100,000이하입니다.nums의 각 원소는-1,000이상1,000이하의 정수입니다.- 세 구간은 모두 연속이어야 합니다.
- 세 구간은 모두 최소 1개 이상의 원소를 가져야 합니다.
예시
- 입력:
nums = [1, 2, 3, 0, 3]→ 출력:true - 입력:
nums = [0, 0, 0]→ 출력:true - 입력:
nums = [1, 1, 1, 1]→ 출력:false - 입력:
nums = [2, 0, 2, 0, 2, 0]→ 출력:true
힌트
- 세 구간의 합이 모두 같으려면 전체 합은 먼저
3으로 나누어떨어져야 합니다. - 목표 합을
target = total / 3이라고 두고, 왼쪽부터 누적합을 쌓아 보세요. - 누적합이
target이 되는 첫 번째 지점과 두 번째 지점을 찾으면 됩니다.
해설
핵심은 전체 합이 3등분 가능한지 먼저 확인하고, 누적합으로 자를 위치를 찾는 것입니다.
- 배열 전체 합을 구합니다.
- 전체 합이
3으로 나누어떨어지지 않으면 바로false입니다. target = total / 3을 구합니다.- 왼쪽부터 누적합을 더하면서
target이 되는 지점을 찾습니다. - 그 뒤 계속 진행해서 누적합이
2 * target이 되는 지점을 마지막 원소 전에 찾으면true입니다.
왜 이렇게 해도 될까요?
- 첫 번째 커트 지점까지의 합이
target - 두 번째 커트 지점까지의 합이
2 * target
이면, 남은 마지막 구간의 합은 자동으로 total - 2 * target = target이 됩니다.
즉 앞의 두 구간만 제대로 찾으면 세 번째 구간도 조건을 만족합니다.
예를 들어 nums = [1, 2, 3, 0, 3]이면 전체 합은 9, 각 구간 목표 합은 3입니다.
[1, 2]의 합은3[3, 0]의 합도3[3]의 합도3
이므로 true입니다.
반대로 nums = [1, 1, 1, 1]의 전체 합은 4라서 애초에 3등분할 수 없습니다.
이 방법은 배열을 한두 번만 순회하므로 시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.