두 큐 합 같게 만들기(2022 KAKAO TECH INTERNSHIP)

문제

코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> queueA=new LinkedList<>();
        Queue<Integer> queueB=new LinkedList<>();
        long queue1Sum=0;
        long queue2Sum=0;
        int maxCount=queue1.length*4;
        int answer=maxCount;
        int count=0;
        for(int i=0;i<queue1.length;i++){
            queueA.add(queue1[i]);
            queueB.add(queue2[i]);
            queue1Sum+=queue1[i];
            queue2Sum+=queue2[i];
        }
        long half=(queue1Sum+queue2Sum)/2;
        if((queue1Sum+queue2Sum)%2!=0) return -1;
        
        while(count<=maxCount){
            if(queue1Sum==half){
                answer=count;
                break;
            }
            if(queue1Sum>half&&queueA.size()>0){
                int item=queueA.poll();
                queueB.add(item);
                queue1Sum-=item;
                count++;
            }
            else if(queue1Sum<half&&queueB.size()>0){
                int item=queueB.poll();
                queueA.add(item);
                queue1Sum+=item;
                count++;
            }
        }
        if(answer==maxCount) return -1;
        return answer;
    }

}

풀이

(1) 입력으로 들어온 배열을 큐(LinkedList)로 만들어준다.(queueA,queueB)
(2) (queueA 원소들의 합 + queueB 원소들의 합)/2를 계산하여 half(각 큐의 원소의 합이 이 값이 되어야 함)변수를 선언해준다.
(3) 두 큐에서 poll(),add()연산을 queueA의 원소의 합이 half가 될 때까지 수행하며 연산시마다 count+1 해준다.

• 연산 수행은 queueA.size()4번 까지 수행한다. 이 안에 조건을 만족시키지 못하면 -1을 반환한다.(처음에는 최대 연산 수행 횟수를 queueA.size()2로 설정하였는데, 테스트케이스 중 하나가 실패했다. 다른사람들의 팁을 보니 queueA.size()*4번까지 해주어야 테스트를 통과한다고 한다. 저 횟수에 대한 정확한 근거는 없다.
• queueA 원소의 합>half 이면 queueA의 원소를 queueB로 옮기고, queueA 원소의 합<half이면 queueB의 원소를 queueA로 옮긴다.
  (4) 위 과정을 반복하다가 queueA의 원소의 합==half가 되면 answer은 count가 된다.

결과

최근 들어, dfs로 풀어야 하는 문제가 많다 보니 이제는 문제를 보면 그쪽으로만 생각하게 된다. 그래서 이 문제도 그렇게 접근했다. 큐를 옮기는 모든 경우의 수를 생각하며 재귀함수를 돌렸더니, 시간초과가 났다. 제한사항을 보면 그럴만도 하다. queue의 길이에 대한 제한이 워낙 크다 보니 시간초과가 나는것이 당연했다. 사실 코드를 짜면서도 이 방법에 의심이 들기는 했다. 하지만 그 당시엔 다른 방법이 생각나지 않았다.
시간초과가 난 후로 계속 다른방법에 대해 생각했다. 아무리 생각해도 가장 적은 횟수를 구하는 방법이 모든 경우의 수를 구해보는 것이 아니라면, 그리디 알고리즘 밖에 없었다.
그래서 dfs()함수를 과감하게 지우고 쉽게 생각했다.
큐의 원소의 합이 half(충족해야 하는 원소들의 합)보다 크면 큐에서 원소를 빼고, half보다 작으면 원소를 더했다. 너무 간단하지만 이게 정답이었다.
좀 더 문제에 대해 생각하는 시간을 신중하게 가져야 할 것 같다. 제한사항도 확인하며, 내가 하고자 하는 방법이 시간초과가 날 위험이 있는지도 확인해야 한다. 문제 유형을 파악하는 것이 알고리즘 해결에 있어서 가장 중요한 것 같다.

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