[프로그래머스/Lv. 2] 두 큐 합 같게 만들기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
 
        long sum1 = 0;  // 1번 큐의 합
        long sum2 = 0;  // 2번 큐의 합
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for(int i = 0 ; i < queue1.length ; i++) {           
            sum1 += queue1[i];
            sum2 += queue2[i];
            
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
                
        long target = (sum1 + sum2) / 2;
        
        while(sum1 != sum2) {
            if(answer >= queue1.length * 3)    // 큐를 최대 3번까지 순회하며 합을 맞출 수 있음
                return -1;
            
            if(sum1 > sum2) {
                sum1 -= q1.peek();
                q2.add(q1.peek());
                sum2 += q1.poll();
            }
            else {
                sum2 -= q2.peek();
                q1.add(q2.peek());
                sum1 += q2.poll();
            }
            
            answer++;
        }
        
        return answer;
    }
}

 

 

 

🧩  해결 아이디어

• 그리디 - 각 큐의 합

- array1의 값을 담은 큐와 array2의 값을 담은 큐를 생성한다.

- 이 두 큐의 값이 합이 다른 경우, 두 값이 같아질 때까지 합이 큰 큐는 맨 앞의 원소를 빼서 작은 큐의 맨 뒤에 값을 더한다.

- 시간 복잡도 : O(N) (∵ 입력값 : 30만)

 

 

💥 유의사항

: queue1.length * 2가 아님! 무조건 길이의 합보다 크게 잡아야 함.

 

---

💬 느낀 점

그리디만 나오면 쫄아버린다.....

쫄지 말자!!!

할 수 있다!!

 

 

1회독	2회독	3회독	4회독	5회독
V	11.23	24.1.21

 

 

(+ 2회독 11.23)

import java.util.*;
 
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0; // 필요한 작업의 최소 횟수
        
        long sum1 = 0;
        long sum2 = 0;
        
        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();
        
        for(int i = 0 ; i < queue1.length ; i++) {
            deque1.add(queue1[i]);
            deque2.add(queue2[i]);
            
            sum1 += queue1[i];
            sum2 += queue2[i];
        }
        
        while(sum1 != sum2) {
            // 큐를 최대 3번까지 순회하며 합 맞출 수 있음
            if(answer >= queue1.length * 3) {
                return -1;
            }
            
            if(sum1 < sum2) {
                deque1.addLast(deque2.peekFirst());
                sum1 += deque2.peekFirst();
                
                sum2 -= deque2.pollFirst();
            }
            else if(sum1 > sum2) {
                deque2.addLast(deque1.peekFirst());
                sum2 += deque1.peekFirst();
                
                sum1 -= deque1.pollFirst();
            }
            
            answer++;
        }        
        
        return answer;
    }
}

---

(참고)

[프로그래머스] lv2 두 큐의 합 같게 만들기 (JAVA)

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