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

지금까지 백준만 풀어오다가 프로그래머스가 좋다는 말에 한걸음에 풀어봤다.

 

시작부터 Lv2문제를 풀어보았다. 주변에서 Lv2문제도 어렵다 하는데 진짜로 너무 어려웠다.

문제를 보자마자 무슨소리를 하는지... 그래도 도전해 보았다.

 

문제를 보자.

두개의 배열이 입력값으로 주어지는데, 각각 배열의 합이 같아야 하고, 한번 이동할때마다 count를 1씩 올려주면 되겠다 싶었다.

 

큐의 성질은 어차피 FIFO 형태로 맨 앞에서만 나가기 때문에 앞에서부터 옮겨주며 합을 비교해주고, 합이 큰 부분에서 가장 앞에 있는 값을 빼 합이 작은 배열로 이동시켜 다시 크기를 비교해보는 방법밖에 생각이 나지 않았다.

 

적혀져 있는 예를 보자.

queue1 = [3, 2, 7, 2] 로 합이 14, queue2 = [4, 6, 5, 1] 로 합이 16으로 queue2의 합이 더 크다.

그러면 queue2의 맨 0번째 값인 4를 queue1에 이동시키고 다시 비교를 해본다.

그러면 queue1의 합이 18, queue2의 합이 12로 queue1의 합이 더 크다. 그러면 다시 queue1의 0번째 값인 3을 다시 queue2로 이동한다. 그러면 queue1의 합과 queue2합이 같아진다.

 

총 2번의 이동에 걸쳐 두 큐의 합이 같이졌다. 그러면 반환되는 값은 2가 된다.

 

JAVA에서 queue 객체를 잘 만들어 뒀다. 나는 Queue 객체를 사용해 진행해보았다.

Queue 객체 2개를 만들고, 각 큐의 합을 넣을 변수, 이동한 횟수를 넣을 변수를 만들었다.

(각 큐의 합을 넣을 변수는 굉장히 큰 수가 나올 수 있으니 long으로 선언해주었다.)

 

그리고 각각 Queue에 테스트데이터의 input으로 들어오는 값들을 넣어주었다.

그리고 선언해준 sum에 각각 큐의 값들을 하나하나 더해 총합으로 만들어주었다.

 

while문을 사용해 두 큐의 합이 같아질때까지 반복하는데, Queue1이 클때와 Queue2가 클때마다 큰쪽에서 작은쪽으로 가장 앞에있는 값을 이동시켜주며 count도 함께 증가할 수 있도록 한다.

만약 두 큐중 하나의 합이 (두 큐의 합 / 2) 과 같을 경우엔 이동한 만큼 센 count를 반환한다.

 

여기서 가장 중요한 점은 총 count수가 queue1의 크기의 3배 이상이 될 때는 두 큐의 합이 같을 수 없다라는 것이다.

(큐의 크기는 같다라는 조건이 있다.)

큐의 순회를 생각해보자. 크기가 5인 큐를 반대쪽에 5만큼 돌려주었을때를 생각해보자. 그러면 이미 count가 5가 된다.

queue1의 크기는 10이 되고, queue2는 0이 된다.

다시 queue1을 queue2로 주었을 때 count는 +=10이 된다.

count는 총 15가 되어 queue1의 원래 크기의 *3이 되는 것이다.

만약 큐 하나의 크기의 3배보다 count값이 크다면 큐의 모든 순회가 종료되어도 답을 찾을 수 없기에 -1을 반환하는 것이다.

 

큐의 순회를 생각하지 않고 풀다 보니 계속되는 오답에 멘탈이 나가버렸었다.

 

큐의 순회를 추가하고 정답을 제출해보니

 

결과는 정답이였다.

문제를 꼼꼼히 살피고, 큐의 순회의 중요성을 깨닫게 되었다.. 아직은 알고리즘에 많이 약한 것 같다... 더욱 다양한 문제를 풀어가며 잘 풀어나갈때까지 노력해보자.

 

전체 코드

public static int solution(int[] queue1, int[] queue2) {
    Queue<Long> q1 = new LinkedList<>();
    Queue<Long> q2 = new LinkedList<>();
    int count = 0;
    long q1_sum = 0;
    long q2_sum = 0;

    for(int i = 0; i < queue1.length; i++) {
        q1_sum += queue1[i];
        q1.add((long) queue1[i]);
    }
    for(int i = 0; i < queue2.length; i++) {
        q2_sum += queue2[i];
        q2.add((long) queue2[i]);
    }

    long mean = (q1_sum + q2_sum) / 2;

    while(true) {
        if(count > queue1.length * 3) return -1;

        if(q1_sum > q2_sum) {
            count++;
            q1_sum -= q1.peek();
            q2_sum += q1.peek();
            q2.add(q1.poll());
        } else if(q1_sum < q2_sum) {
            count++;
            q1_sum += q2.peek();
            q2_sum -= q2.peek();
            q1.add(q2.poll());
        } else {
            if (q1_sum == mean) {
                return count;
            }
            break;
        }
    }

    return count;
}