[프로그래머스/Programmers] 두 큐 합 같게 만들기 (Java - Queue - Lv2)

프로그래머스

---

⭐️ 코드

public int solution(int[] queue1, int[] queue2) {
    int answer = 0; // count를 세는 변수
    // 큐의 합을 저장할 변수
    long q1_Sum = 0L, q2_Sum = 0L;
    // 합 구하기
    for(int i = 0; i < queue1.length; i++){
        q1_Sum += queue1[i];
        q2_Sum += queue2[i];
    }
    // 홀수면 절대 만들 수 없음
    if((q1_Sum+q2_Sum) % 2 != 0) { return -1; }
    // 처음부터 같은 경우
    if(q1_Sum == q2_Sum) { return 0; }
    // 큐
    ArrayDeque<Integer> arrQueue1 = new ArrayDeque<>();
    ArrayDeque<Integer> arrQueue2 = new ArrayDeque<>();
    // 큐 초기화
    for(int i = 0; i< queue1.length; i++){
        arrQueue1.addLast(queue1[i]);
        arrQueue2.addLast(queue2[i]);
    }
    // 찾을 중간 수
    long findNum = (q1_Sum + q2_Sum) / 2;
    // 최대 횟수
    int limit = queue1.length*3;
    // 바꾸는 횟수가 최대 바꾸는 횟수까지 반복
    while(answer <= limit) {
        if (q1_Sum > findNum) {
            q1_Sum -= arrQueue1.peekFirst();
            q2_Sum += arrQueue1.peekFirst();
            arrQueue2.addLast(arrQueue1.pollFirst());
        } else {
            q2_Sum -= arrQueue2.peekFirst();
            q1_Sum += arrQueue2.peekFirst();
            arrQueue1.addLast(arrQueue2.pollFirst());
        }
        answer++;
        if((q1_Sum == findNum)){
            return answer;
        }
    }
    return -1;
}

---

💡 문제 풀이

두 큐의 합이 같도록 만드는 문제인데 가장 최소한으로 수를 바꿔서 값이 같도록 하는 문제다.

 

시간 공간 복잡도

최악의 경우에는 300,000 * 300,000번의 반복을 해야 해서 900억 번의 반복이 일어나게 된다.

또한 큐의 원소의 최대 값은 10^9 이므로 int형이 가질 수 있는 모든 범위의 수보다 벗어나기 때문에 long 타입으로 합을 구해줘야 한다.

하지만 기본적인 원소들은 int타입의 범위에 포함되기 때문에 int형으로 변수를 선언해 줄 수 있다.

 

최대의 반복 제한 횟수는 큐1의 길이 * 3을 해줬는데, 90만 번의 연산이면 웬만하면 모든 경우의 수를 생각할 수 있을 것이라 생각했다. 이 부분은 조금 자세하게 알아볼 필요가 있을 것 같다.

int limit = queue1.length*3;

먼저 실패 코드부터 보자.

실패 코드

import java.util.ArrayDeque;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;

        long q1_Sum = 0L;
        long q2_Sum = 0L;

        ArrayDeque<Long> arrQueue1 = new ArrayDeque<Long>();
        ArrayDeque<Long> arrQueue2 = new ArrayDeque<Long>();

        for(int i = 0; i < queue1.length; i++){
            q1_Sum += (long)queue1[i];
            q2_Sum += (long)queue2[i];
        }
        
        // 홀수면 절대 만들 수 없음
        if((q1_Sum+q2_Sum) % 2 != 0) {
            return -1;
        }

        for(int i = 0; i< queue1.length; i++){
            arrQueue1.addLast((long) queue1[i]);
            arrQueue2.addLast((long) queue2[i]);
        }
        
        long findNum = (q1_Sum + q2_Sum) / 2;
        
        // 최대 횟수
        int limit = queue1.length * 4;

        while(answer <= limit) {
            long switchNum = 0L;
            if (q1_Sum > findNum) {
                switchNum = arrQueue1.pollFirst();
                q1_Sum -= switchNum;
                q2_Sum += switchNum;
                arrQueue2.addLast(switchNum);
            } else {
                switchNum = arrQueue2.pollFirst();
                q2_Sum -= switchNum;
                q1_Sum += switchNum;
                arrQueue1.addLast(switchNum);
            }
            answer++;
            if((q1_Sum == findNum)){
                return answer;
            }
        }
        return -1;
    }
}

솔직히 실패하는 이유를 몰랐었다. 아무리 생각해도 위 코드를 통해서 실패하는 이유는 변수 타입이 알맞지 않아서 일어나는 문제라고 생각했다. 하지만 우리는 한가지 케이스를 생각해야 한다.

바로 처음부터 두 큐의 합은 같은 경우다. queue1_Sum == queue2_Sum

 

성공 코드

public int solution(int[] queue1, int[] queue2) {
    int answer = 0; // count를 세는 변수
    // 큐의 합을 저장할 변수
    long q1_Sum = 0L, q2_Sum = 0L;
    // 합 구하기
    for(int i = 0; i < queue1.length; i++){
        q1_Sum += queue1[i];
        q2_Sum += queue2[i];
    }
    // 홀수면 절대 만들 수 없음
    if((q1_Sum+q2_Sum) % 2 != 0) { return -1; }
    // 처음부터 같은 경우
    if(q1_Sum == q2_Sum) { return 0; }
    // 큐
    ArrayDeque<Integer> arrQueue1 = new ArrayDeque<>();
    ArrayDeque<Integer> arrQueue2 = new ArrayDeque<>();
    // 큐 초기화
    for(int i = 0; i< queue1.length; i++){
        arrQueue1.addLast(queue1[i]);
        arrQueue2.addLast(queue2[i]);
    }
    // 찾을 중간 수
    long findNum = (q1_Sum + q2_Sum) / 2;
    // 최대 횟수
    int limit = queue1.length*3;
    // 바꾸는 횟수가 최대 바꾸는 횟수까지 반복
    while(answer <= limit) {
        if (q1_Sum > findNum) {
            q1_Sum -= arrQueue1.peekFirst();
            q2_Sum += arrQueue1.peekFirst();
            arrQueue2.addLast(arrQueue1.pollFirst());
        } else {
            q2_Sum -= arrQueue2.peekFirst();
            q1_Sum += arrQueue2.peekFirst();
            arrQueue1.addLast(arrQueue2.pollFirst());
        }
        answer++;
        if((q1_Sum == findNum)){
            return answer;
        }
    }
    return -1;
}

아래 코드를 보면 우리는 문제에서 주어진 조건 중 두 큐의 합이 홀수일 때 만들 수 없는 경우를 생각했었다. 

하지만 두 큐의 합이 애초부터 같다면 아래 반복문을 돌릴 필요가 없다.

만약 조건을 주지 않고 실행하면 2번과 29번 케이스에서 시간초과가 난다.

long q1_Sum = 0L, q2_Sum = 0L;
// 합 구하기
for(int i = 0; i < queue1.length; i++){
    q1_Sum += queue1[i];
    q2_Sum += queue2[i];
}
// 홀수면 절대 만들 수 없음
if((q1_Sum+q2_Sum) % 2 != 0) { return -1; }
// 처음부터 같은 경우
if(q1_Sum == q2_Sum) { return 0; }

 

나머지 코드는 어렵지 않다

// 바꾸는 횟수가 최대 바꾸는 횟수까지 반복
while(answer <= limit) {
    if (q1_Sum > findNum) {
        q1_Sum -= arrQueue1.peekFirst();
        q2_Sum += arrQueue1.peekFirst();
        arrQueue2.addLast(arrQueue1.pollFirst());
    } else {
        q2_Sum -= arrQueue2.peekFirst();
        q1_Sum += arrQueue2.peekFirst();
        arrQueue1.addLast(arrQueue2.pollFirst());
    }
    answer++;
    if((q1_Sum == findNum)){
        return answer;
    }
}
return -1;

while문을 통해 반복을 실행하고 반복 횟수가 limit 보다 같거나 작을 때 까지 실행하면 된다. 만약 while문에서 return 하지 않으면 같은 경우가 아예 없기 때문에 -1을 return 해준다.

---

👀 후기

시간을 엄청 쏟았는데 생각보다 풀이가 별거 없다.

하지만 변수 타입별로 실행시간의 차이가 조금씩 났었고, 쓸데없이 선언하는 변수를 제외하고, 반복되는 변수 사용을 줄이니 시간이 더 줄어들었다.