두 대기열의 합을 같게 만드는 최소 이동

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

today medium queue-balancing 함수명: solution 제한 시간: 300ms

문제 설명

두 대기열 queue1, queue2가 주어집니다. 한 번의 이동에서는 한쪽 대기열의 맨 앞 원소를 꺼내 다른 대기열의 맨 뒤에 붙일 수 있습니다.

두 대기열에 들어 있는 숫자의 합이 같아지도록 만드는 최소 이동 횟수를 반환하는 solution 함수를 작성하세요. 어떤 방식으로 이동해도 두 합을 같게 만들 수 없다면 -1을 반환합니다.

예를 들어 queue1 = [3, 2, 7, 2], queue2 = [4, 6, 5, 1]이면 다음처럼 2번 만에 합을 같게 만들 수 있습니다.

queue1 합 14, queue2 합 16
1) queue2의 4를 queue1 뒤로 이동 → queue1 합 18, queue2 합 12
2) queue1의 3을 queue2 뒤로 이동 → queue1 합 15, queue2 합 15

제한사항

queue1과 queue2의 길이는 같습니다.
각 대기열의 길이는 1 이상 100,000 이하입니다.
모든 원소는 1 이상 1,000,000 이하의 정수입니다.
한 번 이동할 때는 반드시 한 대기열의 맨 앞 원소만 꺼낼 수 있습니다.
반환값은 두 대기열의 합을 같게 만드는 최소 이동 횟수이며, 불가능하면 -1입니다.

예시

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

힌트

두 대기열 전체 합이 홀수라면 두 합을 정확히 같게 만들 수 없습니다.
현재 합이 더 큰 대기열에서 원소를 빼서 더 작은 쪽으로 보내야 목표 합에 가까워집니다.
실제 배열에서 shift()를 반복하면 느릴 수 있으니, 앞 위치를 가리키는 인덱스를 움직이는 방식으로 생각해 보세요.

해설

두 대기열의 목표 합은 (queue1 합 + queue2 합) / 2입니다. 전체 합이 홀수라면 목표 합 자체가 정수가 아니므로 바로 -1을 반환할 수 있습니다.

전체 합이 짝수라면 현재 queue1의 합을 기준으로 판단합니다.

queue1의 합이 목표보다 크면 queue1의 앞 원소를 queue2로 보냅니다.
queue1의 합이 목표보다 작으면 queue2의 앞 원소를 queue1로 보냅니다.
queue1의 합이 목표와 같아지는 순간 지금까지의 이동 횟수를 반환합니다.

이때 실제로 원소를 계속 삭제하는 대신, queue1과 queue2를 이어 붙인 배열을 순환 배열처럼 보고 각 큐의 앞 인덱스만 움직이면 효율적으로 처리할 수 있습니다.

주의할 점은 불가능한 경우입니다. 원소들이 계속 반대편으로 넘어가면 이전 상태와 비슷한 상태가 반복될 수 있습니다. 두 큐 길이의 합을 m이라고 할 때, 각 앞 인덱스가 순환 배열을 한 바퀴 이상 지나도록 충분히 확인했는데도 목표 합을 만들지 못하면 더 진행해도 새 상태가 나오지 않습니다. 따라서 이동 횟수에 제한을 두고 그 안에 답을 찾지 못하면 -1을 반환합니다.

각 이동에서 원소 하나만 처리하므로 시간 복잡도는 O(n), 추가 공간은 두 큐를 이어 붙인 배열을 사용할 경우 O(n)입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과