문제 출처	제목	난이도
2022 KAKAO TECH INTERNSHIP	두 큐 합 같게 만들기	Lv.2

두 큐 합 같게 만들기

해결 코드:

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long sum1 = 0;
        long sum2 = 0;
        for(int i=0; i<queue1.length; i++){
            q1.add(queue1[i]);
            sum1 += queue1[i];
            q2.add(queue2[i]);
            sum2 += queue2[i];
        }
        while(sum1 != sum2){
            if(answer > (queue1.length + queue2.length)*2){
                return -1;
            }
            
            if(sum1 > sum2){
                int tmp = q1.poll();
                q2.add(tmp);
                sum1 -= tmp;
                sum2 += tmp;
            }else if(sum1 < sum2){
                int tmp = q2.poll();
                q1.add(tmp);
                sum1 += tmp;
                sum2 -= tmp;
            }else{
                break;
            }
            answer++;            
        }
        
        return answer;
    }
}

고민의 시간과 해결 방법:

1. 문제 자체에서 일단 큐가 나와서 의도가 큐를 쓰겠거니 하였고, 실제로 큐를 활용하는 문제였다.
2. 배열을 순회하면서 각 배열의 원소들의 합을 각각의 sum 변수에 더해주고 큐에도 값을 추가해준다
3. 두 합이 같지 않은동안 순회를 반복하면서 같아질때를 찾는다.
4. 생각한 방법은 한쪽의 합이 더 크면 작은쪽으로 큰 쪽의 값을 큐에서 하나 빼서 넣어주는 방식이다
5. 이 과정에서 sum 변수의 값과 큐의 이동이 일어나고, 시뮬레이션 문제들 처럼 각 while문 순회마다 answer을 증가시킨다
6. 같으면 break해주면된다.
7. 이 방법이 최적의 방법일까? 과연 최소 작업의 횟수를 나타낼 수 있을까? 라는 고민을 하였다.
8. 하지만 생각해보면, 결국 두 수가 같아지려면 옮기는 과정은 꼭 필요하고, 시뮬레이션 방식으로 하나씩 옮기는 방법은 결국 최적의 방법을 구할 수 밖에 없기에 해당 방법의 문제는 없다고 결론을 내렸다
9. 이어서 이 순회는 자칫하면 무한루프에 빠질 수 있다. 따라서 종료조건을 하나 생각해야한다
10. 일단 처음 생각한 것은 두 배열의 크기를 더한것 만큼 정도만 돌면 되지 않을 까 싶었다. 테스트케이스에서는 통과했는데 제출에서 틀렸다..
    (실제 코딩테스트였으면 최악의 경우...)
11. 그렇다면 어떻게 종료조건을 주어야할까에 대한 고민을 하였고 결국 그 답은 카카오 테크의 해설을 통해 확인할 수 있었다
12. 여기서는 투포인터 방식으로도 풀 수 있다고 하였다. 두 큐를 하나로 합쳐서 하나의 배열로 바라보았다. 이때 배열의 크기는 2n이다.
13. 따라서 한 포인터당 최대 2n번을 돌아야 하며, 두개의 포인터가 돌고 있으므로 4n번은 돌아주어야한다.
14. 위 방식으로 했을 때 잘 통과하는데... 찜찜해서 더 풀이를 찾아보았더니 2n + 1은 안 되고 2n+2는 통과되는 모습을 확인할 수 있었다
15. 제출 케이스가 부족해서 발생하는 문제인건지 아니면 다른 문제인건지는 모르지만 이 부분에 대해서는 두 배열을 합쳐서 하나의 배열로 바라보았다는 점과 한 포인터가 한 큐라고 생각하고 두 포인터가 각각 최대로 돌 수 있는건 2n이니까 4n번 돌아야한다! 라는 논리를 학습해가는 것만으로 만족하려고 한다.

문제링크:

두 큐 합 같게 만들기

참고링크: 2022 테크 여름 인턴십 코테 문제 해설