[Java] 프로그래머스 - 두 큐 합 같게 만들기(lv.2)

못푼 이유

• 큐를 만들어 사용할까 고민하다 주어진 배열을 그대로 사용해 풀기로 함. 하지만 배열 카피 지옥에 빠졌고 수많은 예외처리가 발생해 구현에 실패했다.
• 아래 핵심로직을 파악 못하고 첫번째 큐에서 pop하는 경우, 두번째 큐에서 pop하는 경우를 이진트리를 구현해 푸려고 했다. 물론 구현했다면 풀렸을테지만, 아래 로직을 파악하고 반복문으로 푸는게 더 효율적이고 구현 난이도도 낮다.

 

 

핵심 로직

• 각 큐의 합이 큰 쪽을 pop(poll), 작은 쪽에 insert(offer)
• 요소의 이동 횟수가 큐의 길이 * 3 보다 커질경우 합이 같아 질 수 없는 것으로 간주, -1을 리턴

소스 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long sum1 = 0;
        long sum2 = 0;
        
        for(int i=0; i<queue1.length; i++){
            sum1+=queue1[i];
            sum2+=queue2[i];
            
            q1.offer(queue1[i]);
            q2.offer(queue2[i]);
        }
        int maxCount = queue1.length*3;
        
        while(sum1!=sum2){
            if(maxCount-answer==0){
                return -1;
            }
            answer++;
            
            if(sum1>sum2){
                int polled = q1.poll();
                sum1-=polled;
                sum2+=polled;
                
                q2.offer(polled);
                continue;
            }
            int polled = q2.poll();
            sum2-=polled;
            sum1+=polled;
            
            q1.offer(polled);
        }
        
        return answer;
    } 
}

 

깨달은 점

예제 케이스를 직접 풀어보면서 규칙을 발견했더라면 해결할 수 있었을 것이다. 그리고 자료구조도 적극 활용하자.