[프로그래머스] Lv.2 두 큐 합 같게 만들기 문제 해결 과정(Java)

 문제링크

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

프로그래머스

 

 

 해결 과정

 문제 이름에서부터 큐(Queue)가 있어서 큐를 사용해야 할 것 같았지만, 큐를 사용하지 않고, 배열만 가지고 구현해 보는 방향으로 생각했다.

 

 문제를 풀기 앞서서 가장 의문이 들었던 점은 "두 큐에서 정수를 추출하고 삽입하는 과정을 몇 번을 해야 초기상태와 같아질까?"였다. 왜냐면 큐는 FIFO(First-In First-Out)형 자료구조이기 때문에 언젠가는 초기 상태와 같아질 것이라고 생각했다. 문제에서는 최소한의 횟수를 요구했기 때문에, 이러한 사이클 형성하는 최소한의 개수부터 탐색해 보기로 했다.

 

 사이클 개수 구하는 과정

 현재 큐 A, B에 각각 [1, 2, 4, 5], [2, 5, 8, 9]이 있다고 생각해보자

 각 큐에 있는 모든 정수들을 서로 다른 큐로 옮기려면 총 8번의 연산을 수행해야 한다. 

 

서로 다른 큐에 있는 정수들을 다시 초기 상태로 만들려면 역시 8번의 연산을 수행해야 한다.

즉, 각 큐에 4개씩 있을 때, 총 16번의 연산을 통해서 한 사이클을 만들 수 있다.

이를 코드로 표현하면 다음과 같이 나타낼 수 있다.

public int solution(int[] queue1, int[] queue2) {
    int answer = -1;
    //4를 곱한 이유는 문제에서 queue1과 queue2의 원소의 길이가 같다고 제시.
    int cycle = 4*queue1.length;
    ,,,
}

 

 그러면 이 문제는 한 사이클 내에 두 큐의 합이 같아지면 그 횟수를 아니면 -1을 반환하면 되는 문제로 바뀌게 된다.

 

 두 큐의 합이 같은지 비교를 하기 위해서 아래 과정을 반복했다.

• 현재 각 큐에 있는 모든 원소의 합을 구하여 합이 같으면 연산을 적용한 횟수를 반환, 그렇지 않으면 아래 작업을 수행한다.
• 두 큐 중 합이 큰 큐에서 작은 큐로 원소를 하나 삽입한다.
• 한 사이클을 돌려도 합이 같아지지 않으면 -1을 반환한다.

 근데 이를 자료구조 사용하지 않고 구현했더니 시간 초과가 발생했다. 지금 생각해 보면 큐의 offer(), poll() 메서드를 잘못 구현한 것 같았다. 내가 구현한 방식은 poll()과 offer() 연산을 수행할 때마다 반복문으로 처리를 했는데 이 부분에서 수행 시간이 많이 소요된 것 같았다.

 

 그래서 일단 이 방법은 잠시 접어두고 자료구조를 사용해서 해결했다.

수행 결과

 

 

 전체 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        //두 큐가 연산을 수행하며 초기 상태와 같아지는 횟수를 구한다.
        int cycle = 4*queue1.length;
        
        //각 큐에 원소를 집어넣으면서 합을 구함.
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2  = new LinkedList<>();
        long sum1 = getSum(queue1, q1);
        long sum2 = getSum(queue2, q2);
        //두 큐의 합이 홀수면 -1을 반환
        if((sum1+sum2) % 2 == 1) return answer;
        
       	//한 사이클 이내에서 큐의 합이 같은 지 수행.
        for(int count = 0; count < cycle; count++) {            
            int element;
            //두 큐의 합이 같으면 연산 횟수를 반환한다.
            if(sum1 == sum2) {
                return count;
            }
            else if(sum1 > sum2) {
                element = q1.poll();
                q2.offer(element);
                sum1 -= element;
                sum2 += element;
            } else {
                element = q2.poll();
                q1.offer(element);
                sum1 += element;
                sum2 -= element;
            }
        }
        //한 사이클만큼 연산을 수행해도 같아지지 않으면 -1을 반환한다.
        return answer;
    }
    
    private long getSum(int[] queue, Queue<Integer> q) {
        long sum = 0;
        for(int i = 0; i < queue.length; i++) {
            q.offer(queue[i]);
            sum += queue[i];
        }
        return sum;
    }
}

 

 

 정리 및 회고

• 사실 두 큐의 합이 홀수인 경우도 있을 것 같아서 오답 방지차원에서 했는데 없어도 잘 풀렸다. 뭔가 문제가 생각보다 친절했다.
• 그리고 배열만 사용하는 것이면 반복문이 아니라 각 큐에 커서를 배치해서 이를 가지고 했어야 됐나 싶은 생각이 들었다. 나중에 코테 문제가 어려워서 풀기 힘들어지면 해봐야겠다.