[프로그래머스] Java Lv2. 코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 두 큐 합 같게 만들기

 

프로그래머스

문제설명

길이가 같은 두 개의 큐가 주어진다.

하나의 큐를 골라 원소를 추출(pop)하고 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만드려고 한다.

한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주한다.

각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 반환하도록 하고 불가능할 경우 -1을 반환한다.

제한사항

• 1 <= queue1의 길이 = queue2의 길이 <= 300,000
• 1 <= queue1의 원소, queue2의 원소 <= 10^9

접근방법

문제에도 나와있다싶이 queue의 원소가 10억 이하이므로 하나의 큐의 합이 최대 10억 * 300,000이 될 수 있으니 합계는 long을 사용하여 구한다.

목표가 되는 큐의 합을 미리 구해 목표에 근접해지는 방향으로 queue의 pop과 insert를 유도할 수 있다.

두 큐의 합계를 모두 구할필요는 없고, index를 활용하면 주어진 리스트를 그대로 활용할 수 있다.

while의 반복 최댓값을 구해 -1 return을 위한 기준을 판단한다.

queue는 FIFO이므로 마지막에 있는 원소가 반대쪽으로 이동할 경우 length만큼 answer가 증가하게 된다.

따라서 최대 반복횟수는 2*length번이 된다

핵심로직

• 전체 합과 계산 기준으로 삼을 queue1의 합(sum1)을 구하고 목표 합(goalSum)을 설정한다 (sum / 2)
• sum1 목표 합과 같아질 때까지 반복
  • sum1이 목표합보다 작을경우 index2를 증가시킨 후 해당 숫자를 sum1에서 증가
  • sum1이 목표합보다 클경우 index1을 증가시킨 후 해당하는 숫자를 sum1에서 차감
  • index가 queue의 length보다 커질 경우 다른 queue에 원소가 차곡차곡 쌓였다는 의미이므로 다른 queue에서 원소를 탐색
  • answer가 queue length *2 + 2보다 커질경우 -1반환

입출력 예

• queue1 = [3, 2, 7, 2]
• queue2 = [4, 6, 5, 1]
• result = 2

코드작성

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum = 0L;
        long sum1 = 0L;
        // 합 계산
        for(int i=0; i<queue1.length; i++) {
            sum += queue1[i];
            sum1 += queue1[i];
            sum += queue2[i];
        }
        long goalSum = sum/2L;
        if(goalSum*2 != sum) {
            return -1;
        }
        int index1 = 0;
        int index2 = 0;
        // 목표 합계 구하기
        while(sum1 != goalSum) {
            if(sum1 < goalSum) {
                if(index2 < queue2.length) {
                    sum1 += queue2[index2];    
                } else {
                    // queue2의 index가 length를 넘어가게 될 경우 해당 원소는
                    // queue1로부터 온 것이므로 queue1에서 탐색
                    sum1 += queue1[index2%queue1.length];
                }
                index2 ++;
            } else {
                if(index1 < queue1.length) {
                    sum1 -= queue1[index1];
                } else {
                    sum1 -= queue2[index1%queue2.length];
                }
                index1 ++;
            }
            
            answer ++;
            if(sum1 == goalSum) {
                break;
            }
            
            // 한바퀴씩 다 돌리고 났는데도 결론이 안났다면 -1 반환
            if(answer > queue1.length*2 + 1) {
                answer = -1;
                break;
            }
        }

        return answer;
    }
}