[프로그래머스] 두 큐 합 같게 만들기 - 2022 KAKAO TECH INTERNSHIP

문제링크 🚩

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

​

📕 문제 접근 📕

큐를 이용하여 그리디한 접근

각 큐의 합을 기준으로 그리디 하게 접근하였습니다.

합이 큰 쪽에서 작은쪽으로 숫자를 추출하여 더하는 과정을 양쪽 큐가 같을 때까지 반복하였다.

최악의 길이는 현재 큐의 길이를 한 바퀴 더 도는 경우인 length * 2일 것 이다. 하지만 큐가 2개 이기 때문에 최악의 경우는 위의 경우에서의 * 2배이다.

 

로직설명

- 문제 제공 queue1, queue2로부터 새로운 두 개의 큐를 생성(q1, q2) 및 각각의 합(sum1, sum2) 구하기

- 양쪽 큐가 원래 상태로 돌아올때까지 반복:

1) sum1 > sum2인 경우: q1에서 poll() 후 q2에 add(), 각각의 합 증감

2) sum1 < sum2인 경우: q2에서 poll() 후 q1에 add(), 각각의 합 증감

3) sum1 == sum2인 경우: answer에 횟수 저장 후 반복 종료

 

💻 Code 💻

 

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        
        //큐 선언
        Queue<Integer> q1 = new LinkedList<Integer>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        
        // 합 변수 선언
        long sum1 = 0;
        long sum2 = 0;
        
        for(int num : queue1){
            q1.add(num);
            sum1 += num;
        }
        
        for(int num : queue2){
            q2.add(num);
            sum2 += num;
        }
        
        int cnt = 0;
        while(cnt < queue1.length * 2 * 2){
            if(sum1 > sum2){
                int num = q1.poll();
                sum1 -= num;
                sum2 += num;
                q2.add(num);
            }else if(sum1 < sum2){
                int num = q2.poll();
                sum2 -= num;
                sum1 += num;
                q1.add(num);  
            }else if(sum1 == sum2){
                answer = cnt;
                break;
            }
            cnt++;
        }
    
         return answer;
    }
}