왼쪽과 오른쪽 합이 같은 첫 분기점

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

today easy pivot-scan 함수명: firstBalancedPivot 제한 시간: 200ms

배열에서 왼쪽 합과 오른쪽 합이 같아지는 첫 번째 위치를 찾는 문제입니다.

문제 설명

정수 배열 nums가 주어집니다.

어떤 인덱스 i를 기준으로 했을 때,

i의 왼쪽에 있는 모든 원소의 합
i의 오른쪽에 있는 모든 원소의 합

이 서로 같다면 그 인덱스를 분기점이라고 하겠습니다.

배열에서 이런 조건을 만족하는 가장 작은 인덱스를 반환하는 firstBalancedPivot 함수를 작성하세요. 조건을 만족하는 위치가 없으면 -1을 반환합니다.

제한사항

nums의 길이는 1 이상 100,000 이하입니다.
nums의 각 원소는 -10,000 이상 10,000 이하의 정수입니다.
반환값은 조건을 만족하는 가장 작은 인덱스이며, 없으면 -1입니다.
인덱스의 한쪽에 원소가 하나도 없으면 그쪽 합은 0으로 봅니다.

예시

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

힌트

매번 왼쪽과 오른쪽을 다시 더하면 너무 느립니다.
먼저 배열 전체 합을 구해 두면, 현재 위치의 오른쪽 합은 빠르게 계산할 수 있습니다.
순회하면서 왼쪽 누적합을 하나씩 업데이트해 보세요.

해설

핵심은 배열 전체 합과 왼쪽 누적합을 함께 활용하는 것입니다.

먼저 전체 합을 total이라고 합시다. 인덱스 i를 보고 있을 때:

왼쪽 합은 지금까지 누적한 leftSum
오른쪽 합은 total - leftSum - nums[i]

가 됩니다.

따라서 매 위치마다 다음 순서로 확인하면 됩니다.

rightSum = total - leftSum - nums[i]를 계산합니다.
leftSum === rightSum이면 그 인덱스를 바로 반환합니다.
아니라면 leftSum += nums[i]로 현재 값을 왼쪽 합에 포함시키고 다음 칸으로 넘어갑니다.

예를 들어 nums = [1, 7, 3, 6, 5, 6]이면 전체 합은 28입니다.

i = 0: 왼쪽 0, 오른쪽 27
i = 1: 왼쪽 1, 오른쪽 20
i = 2: 왼쪽 8, 오른쪽 17
i = 3: 왼쪽 11, 오른쪽 11 → 정답

또 nums = [2, 1, -1]에서는 맨 앞 인덱스 0에서

왼쪽 합은 0
오른쪽 합은 1 + (-1) = 0

이므로 바로 0이 정답입니다.

이 방법은 전체 합을 한 번 구하고, 다시 한 번 순회하므로 시간 복잡도는 O(n)이고 추가 공간은 O(1)입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.