[코딩테스트][프로그래머스] 두 큐 합 같게 만들기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3

python

from collections import deque

def solution(queue1, queue2):
    answer = 0
    
    isCanMake=False
    len_q1=len(queue1)
    len_q2=len(queue2)
    q1=deque(queue1)
    q2=deque(queue2)
    
    # 큐의 넣음과 뺌이 연속됨을 유지하므로 각 배열을 연결한 뒤 2배한 것에서 찾을 수 있다.
    total_q=(queue1+queue2)*2
    target_sum_value=sum(queue1+queue2)/2
    
    # 두개의 합이 홀수가 되어 둘로 나누어질 수 없을 경우
    if target_sum_value-int(target_sum_value)>0:
        return -1
    
    # 이미 각 배열의 합이 같을 경우
    if sum(queue1)==sum(queue2):
        return 0
    
    q1=deque(queue1)
    q1_sum=sum(queue1)
    q2=deque(queue2)
    q2_sum=sum(queue2)
    while True:
        if answer>650000:
            break
        if q1_sum>q2_sum:
            k=q1.popleft()
            q2.append(k)
            q1_sum-=k
            q2_sum+=k
            answer+=1
        elif q1_sum==q2_sum:
            return answer
        elif q1_sum<q2_sum:
            k=q2.popleft()
            q1.append(k)
            q2_sum-=k
            q1_sum+=k
            answer+=1
        
    
    # 두개의 배열로 나누었을 때, 합이 최종적으로 나누어질 수 없는 경우
    if not isCanMake:
        return -1
    
    return answer

java

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

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        
        Queue<Integer> q1=new LinkedList<Integer>();
        Queue<Integer> q2=new LinkedList<Integer>();
        for(int i : queue1){
            q1.offer(i);
        }
        for(int i : queue2){
            q2.offer(i);
        }
        long sum_value_q1=0;
        long sum_value_q2=0;
        for(int i : q1){
            sum_value_q1+=i;
        }
        for(int i : q2){
            sum_value_q2+=i;
        }
        
        if((sum_value_q1+sum_value_q2)%2!=0){
            
            return -1;
        }
        if(sum_value_q1==sum_value_q2){
            return 0;
        }
        boolean canMake=false;
        while(true){
            if(answer>1000000){
                break;
            }
            if(sum_value_q1>sum_value_q2){
                int k=q1.poll();
                q2.offer(k);
                answer+=1;
                sum_value_q1-=k;
                sum_value_q2+=k;
            }else if(sum_value_q1==sum_value_q2){
                return answer;
            }else{
                int k=q2.poll();
                q1.offer(k);
                answer+=1;
                sum_value_q2-=k;
                sum_value_q1+=k;
            }
        }
        
        if(!canMake){
            return -1;
        }
        
        return answer;
    }
}

내 풀이

• 풀이시간 : 1시간
• 처음에는 데이터양을 보고 O(nlogn)알고리즘으로 접근해볼려고 하다가 아이디어가 안나와서 한참을 해맸다. 중간부터는 모든 데이터를 회전시켜 큐가 순환구조인 것을 사용하려고 하였으나 시간복잡도 면에서 해결을 못하기도 하였고 횟수를 구하는 면에서 두개의 배열을 실제로 구해내도 몇번인지 다시 찾아야한다는 문제가 있었다.
• 그러다가 더 간단히 해보자는 면에서 접근하였다가 방법에 도달하였는데 단순히 각 큐의 담겨있는 원소의 합의 크기를 비교해서 같아질 때까지 큰쪽의 원소를 작은 쪽의 원소를 문제의 방법으로 옮기는 것이다. 이렇게 하면 같아질 때까지 작업을 반복하면 같아지거나 불가능한 경우가 발생한다.