[자바] 프로그래머스 - 두 큐 합 같게 만들기 (Lv2, Java)

문제 : Programmers-두 큐 합 같게 만들기

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

필요 알고리즘 개념

• 그리디
  
  • 어떠한 규칙을 정해, 해당 규칙대로 진행하다보면 답이 나오게 되는 그리디 유형의 문제이다. 
• Queue
  
  • FIFO (선입선출) 특징을 가지는 큐에 대한 개념이 있어야 구현할 수 있다.

 

 

  두 큐에 들어있는 모든 값들의 합을 sum이라 하자. 결국 우리가 알고 싶은건 한쪽 큐의 합이 sum/2를 가지게 하는 최소 횟수이다. (sum이 홀수인 경우라면 불가능한 경우이니 -1을 출력하면 된다)

 

  모든 경우를 우선 생각해보자. queue1에 들어있는 값들의 합을 s1, queue2의 모든 값들의 합을 s2라고 하겠다.

1. 처음부터 s1 == s2

2. queue1에서 특정 n개(연속되지 않아도 된다)를 queue2로 옮기는 경우

3. queue2에서 queue1으로 n개를 옮기는 경우

 

  위의 과정으로 s1과 s2를 같게 만드는 경우가 있는지 확인은 할 수 있다. 하지만 이 문제에서 요구하는건 옮기는 횟수의 최소수치이다. 근데 어차피 queue1과 queue2에 존재하는 모든 값은 1부터 10^9으로 양수이다. 따라서, queue1에서 queue2로 옮기면 항상 s1은 줄어들고, s2는 증가한다. 그 반대도 마찬가지다. 그렇다면, sum/2 보다 s1이 크다면 queue1에서 queue2로 옮기고, sum/2 보다 s2가 크다면 queue2에서 queue1으로 옮긴다는 규칙을 만들어보면 어떨까? 만약 음수가 존재했다면 이런 방식으로 힘들겠으나 양수만 존재하고 queue의 FIFO를 따르므로 어차피 중간의 값을 옮길 수 없으므로 이 규칙대로 진행하면 정답이 될 수 있다.

 

  따라서 로직은 다음과 같다.

1. queue1의 합 s1, queue2의 합 s2를 구한다. 전체 값의 합 sum = s1+s2 이다.

2. sum이 홀수라면 -1을 리턴한다.

3. 이후 s1==s2가 될 때 까지 s1이 sum/2보다 크다면 queue1에서 queue2로 값을 옮긴다(s1감소, s2증가). s2가 sum/2보다 크다면 queue2에서 queue1으로 값을 옮긴다.

4. s1==s2인 경우가 없다면 -1을 리턴해준다.

 

  만약 s1이 sum/2보다 크지만, queue2에서 queue1으로 먼저 옮기는게 이득인 경우가 있을까? 동일한 경우는 있어도 이득인 경우는 없다. 한번 해당 예시를 만들어보려고 노력해보면 결국 동일한 경우가 최선임을 알 수 있다.

 

  로직에서 '4'는 언제까지 진행해야 알 수 있을까? 대강 최악의 경우를 생각해보면, queue1과 queue2의 값들을 서로 전부 교환하는 경우 대략 길이의 2배만큼 필요하다.

따라서 queue1에서 queue2로 이동한 횟수, queue2에서 queue1이 각각 처음 큐 길이의 2배만큼 진행되면 모두 봤다고 가정하면 된다. 어차피 N=30만이므로 대략 정해도 된다. 예를들어 queue1에서 queue2로 이동한 횟수 + queue2에서 queue1으로 이동한 횟수가 처음 큐길이의 3배만큼 정도로 정해도 통과 된다.

 

 

코드 : github

import java.util.ArrayDeque;
import java.util.Queue;
/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();
        long s1=0, s2=0, sum;
        for (int tmp : queue1) {q1.add(tmp); s1+=tmp;}
        for (int tmp : queue2) {q2.add(tmp); s2+=tmp;}
        sum = s1+s2;
        if (sum%2==1) return -1;
        sum/=2;
        int p1 = 0, p2 = 0, limit = queue1.length*2;
        while (p1<=limit && p2<=limit) {
            if (s1 == sum) return p1+p2;
            if (s1>sum) {
                s1-=q1.peek();
                s2+=q1.peek();
                q2.add(q1.poll());
                p1++;
            } else {
                s2-=q2.peek();
                s1+=q2.peek();
                q1.add(q2.poll());
                p2++;
            }
        }
        return -1;
    }
}