프로그래머스(카카오) | LV.2 두 큐 합 같게 만들기 - 큐(Queue) 활용 문풀 (Java)

⬛ 프로그래머스(카카오) | LV.2 두 큐 합 같게 만들기 - 큐 (Queue) 활용 문풀 (Java)

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

프로그래머스

문제 설명

---

💚 문제 접근 방식

문제를 보고 매번 큰 합의 큐에서 poll하고 작은 합의 큐에 add 해야 되겠다는 생각이 가장 먼저 들었다.

1. Queue 2개 선언해서 각각의 큐에 원소값을 세팅한다.
2. 동시에 두 큐의 총합을 total 에 구하고, 한쪽의 sum만 구해둔다.
3. 만약 total 이 홀수값이라면 각 큐의 총합이 같게 분배 자체가 불가능하다. 이 경우 -1 리턴
4. while문을 돌며 한쪽큐의 합과 target(총합의절반)을 비교하며 처리를 이어나간다.
5. 만약 count가 두 큐 길이합의 2배보다 크다면 구할 수 없으니 -1 리턴
6. sum1과 total이 같다면 count 리턴

---

1차 시도

• sum1, sum2 각각 구해놓고, 매번 sum 값이 더 큰 쪽에서 poll() 하여 작은 쪽에 offer() 처리를 했다.
• 이 경우, 예제 케이스는 통과했지만, 최종 제출 시에는 실패가 떴다.
• 일단 while문의 종료 조건 주는 부분도 둘 중 하나의 sum이 0이 될 경우 못 구한다고 생각하고 -1을 리턴했었는데 생각해보면 반드시 그런 것도 아니다.

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Long> Q1 = new LinkedList<>();
        Queue<Long> Q2 = new LinkedList<>();
        
        Long sum1 = Long.valueOf(0);
        Long sum2 = Long.valueOf(0);
        
        for(int x : queue1) {
            Q1.offer(Long.valueOf(x));
            sum1 += Long.valueOf(x);
        }
        
        for(int x : queue2) {
            Q2.offer(Long.valueOf(x));
            sum2 += Long.valueOf(x);
        }
		if( (sum1+sum2) % 2 != Long.valueOf(0)) return -1;
        int count = 0;
				
        while(sum1 != sum2){
        //종료 조건을 둘 중 하나가 0이 되는 거로 했는데 이것도 완벽하진 않다.
        //예를 들어. 한 큐가 다 빈 상태에서 마지막 poll한 값 넘겨줄 때 두 sum이 같아지기도 하니까 
	        if(sum1 == 0 || sum2 == 0) return -1;
            if(sum1 > sum2){
                Q2.offer(Q1.peek());
                sum1 -= Q1.peek();
                sum2 += Q1.peek();
                Q1.poll();
            }else if(sum2 > sum1){
                Q1.offer(Q2.peek());
                sum2 -= Q2.peek();
                sum1 += Q2.peek();
                Q2.poll();
            }
            count++;
        }
        return count;
    }
}

---

2차 시도

• 한쪽의 합만 활용해도 됐다는 것과 종료 조건을 생각해내지 못한 것이 아쉽다.

1) 두 큐의 길이가 같다는 것을 활용해 1번의 순회로 두 큐에 값을 담고 total 을 구할 수 있었다.

2) 굳이 sum1, sum2 모두 활용하지 않고, total과 한쪽의 합만 활용해서 total의 절반값과 비교하며 풀면 됐다.

3) 또한, 종료 조건에서 count가 두 큐의 길이 합의 2배보다 클 경우 → 어떤 방법으로도 두 큐의 원소 합을 같게 만들 수 없는 경우가 된다.

💚 제출 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Long> Q1 = new LinkedList<>();
        Queue<Long> Q2 = new LinkedList<>();
        
        long sum1 = 0;
        long total = 0;
        //두 큐 사이즈가 같기 때문에 한번의 순회로 합과 Q에 add 처리 가능 
        for(int i=0; i<queue1.length; i++){
            total += (queue1[i] + queue2[i]);
            Q1.offer(Long.valueOf(queue1[i]));
            Q2.offer(Long.valueOf(queue2[i]));
            sum1 += queue1[i];
        }

		if( total % 2 != 0) return -1;
        
        long target = total / 2; //타겟 값 
        
        int count = 0;
				
        while(true){
	        // 넉넉 잡아 두 바퀴를 돌아도 안되면 안됨
            if(count > (queue1.length+queue2.length) *2) return -1;
            if(sum1 == target) break;
            if(sum1 > target){
                sum1 -= Q1.peek();
                Q2.offer(Q1.poll());
            }else{
                sum1 += Q2.peek();
                Q1.offer(Q2.poll());
            }
            count++;
        }
        return count;
    }
}

💚 회고

예제만 통과하고 최종에서 실패가 뜨면 내가 뭔가 더 고려하지 못한 거라는 뜻이다. 더 나은 방식과 효율적인 방식을 고민해야 되는데 구현에 급급해서 세밀하게 처리를 못하는 것 같다 ㅠㅠ