[JAVA] 프로그래머스 level2 두 큐 합 같게 만들기

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

프로그래머스

코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP  > 두 큐 합 같게 만들기

 

문제 접근

처음 접근은 단순하게 각 큐의 크기를 비교하면서 왼쪽큐가 크면 왼쪽큐에서 원소를 빼서 오른쪽 원소에 추가 

오른쪽큐가 크면 오른쪽 큐에서 원소를 빼서 왼쪽 원소에 추가를 반복하였다. 

이렇게 푸니까 시간초과가 발생했다. 

시간 초과 코드(93점)

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        long s1  = 0;
        long s2  = 0; 
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        for(int i = 0; i < queue1.length; i++){
            q1.add(queue1[i]);
            q2.add(queue2[i]);
            s1 += queue1[i];
            s2 += queue2[i];
        }
        int answer = 0;
      
        while(!q1.isEmpty() && !q2.isEmpty()){
            if(s1 == s2) return answer;
            
            answer++;
            
            if(s1 > s2){
               int target = q1.poll();
               s1 -= target;
               s2 += target;
               q2.add(target); 
            }
            else{ // s1 < s2
               int target = q2.poll();
               s2 -= target;
               s1 += target;
               q1.add(target); 
            }
        }        
        return -1;
    }
}

 

이렇게 문제를 풀면  2가지 테스트 케이스에서 무한 반복 구간이 생긴다. 

 

반례

queue1(int[]) [1,1,1]

queue2(int[]) [1,1,2]

return -1

 

개선 방법 

어떻게 하면 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 케이스를 효율적으로 구할까 생각을 계속해 보았다.

내가 생각한 방법은 원소의 위치를 기억하고 해당 원소가 움직여서 다시 처음 시작한 위치로 돌아온다면 

해당 케이스는 불가능한 케이스겠구나를 생각해 냈다. 

 

그래서 큐 원소를 Integer 에서 배열로 바꾸었다. 

 

배열의 인덱스 의미

0: 처음 원소의 인덱스

1: 원소의 크기 

2: 큐1 소속? or 큐2 소속? 

long s1  = 0;
long s2  = 0; 
ArrayDeque<int[]> q1 = new ArrayDeque<>();
ArrayDeque<int[]> q2 = new ArrayDeque<>();
for(int i = 0; i < queue1.length; i++){
    q1.add(new int[]{i, queue1[i], 1});
    q2.add(new int[]{i, queue2[i], 2});
    s1 += queue1[i];
    s2 += queue2[i];
}

 

해당 정보를 바탕으로 처음 시작한 위치로 돌아오면 return -1 통해서 종료를 하는 로직을 만들었다.

if(temp[0] == 0 && temp[2] == 1){
  	cnt1++;
  	if(cnt1 == 2) return -1;
}

 

cnt 값이 2인 경우는 처음 로직이 돌아가면 1로 시작하기 때문에 바로 종료되는 케이스가 있다. 

그래서 2로 조건을 만들었다.

정답(전체) 코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        long s1  = 0;
        long s2  = 0; 
        ArrayDeque<int[]> q1 = new ArrayDeque<>();
        ArrayDeque<int[]> q2 = new ArrayDeque<>();
        for(int i = 0; i < queue1.length; i++){
            q1.add(new int[]{i, queue1[i], 1});
            q2.add(new int[]{i, queue2[i], 2});
            s1 += queue1[i];
            s2 += queue2[i];
        }

        int answer = 0;
        int cnt1 = 0;
        int cnt2 = 0; 
        
        while(true){
            if(s1 == s2) return answer;
            answer++;
            if(s1 > s2){
               int [] temp = q1.poll();
               if(temp[0] == 0 && temp[2] == 1){
                  cnt1++;
                  if(cnt1 == 2) return -1;
               }
               s1 -= temp[1];
               s2 += temp[1];
               q2.add(temp); 
            }
            else{ // s1 < s2
               int [] temp = q2.poll();
               if(temp[0] == 0 && temp[2] == 2){
                  cnt2++;
                  if(cnt2 == 2)   return -1;
               }
               s2 -= temp[1];
               s1 += temp[1];
               q1.add(temp); 
            }
        }
    }
}