문제 링크

문제 간단 해석

큐 2개의 시점으로, 양 쪽의 값이 같아지는 최소횟수를 구하는 문제.
자바와 파이썬의 풀이가 약간 다르다. 더 나은 방법에 대해 생각해보자.

Java

큐 2개를 지닌 객체를 만들고 연산을 했다.

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public static class TwinQueue {
        private Queue<Long> queue1;
        private Queue<Long> queue2;
        private long now;
        private long target;
        private int count = 0;
        
        TwinQueue(List<Long> list1, List<Long> list2, long sum1, long sum2) {
            queue1 = new LinkedList(list1);
            queue2 = new LinkedList(list2);
            now = sum1;
            target = (sum1 + sum2) / 2;
        }
        
        public int makeEqual() {
            while (target != now) {
                try {
                    if (now < target) {
                        long l = queue2.remove();
                        queue1.add(l);
                        now += l;
                    } else if (now > target) {
                        now -= queue1.remove();
                    }
                } catch(Exception e) {
                    return 1000000;
                }
                count++;
            }
            return count;
        }
    }
    
    public int solution(int[] queue1, int[] queue2) {
        long sum1 = Arrays.stream(queue1).asLongStream().sum();
        long sum2 = Arrays.stream(queue2).asLongStream().sum();
        
        if ((sum1 + sum2) % 2 == 1)
            return -1;
        
        List<Long> list1 = Arrays.stream(queue1).asLongStream().boxed().collect(Collectors.toList());
        List<Long> list2 = Arrays.stream(queue2).asLongStream().boxed().collect(Collectors.toList());
        
        TwinQueue twinQueue1 = new TwinQueue(list1, list2, sum1, sum2);
        TwinQueue twinQueue2 = new TwinQueue(list2, list1, sum2, sum1);
        
        int result1 = twinQueue1.makeEqual();
        int result2 = twinQueue2.makeEqual();
        int result = Math.min(result1, result2);
        
        if (result == 1000000)
            return -1;
        
        return result;
    }
}

해석

클래스

public static class TwinQueue {
    private Queue<Long> queue1;
    private Queue<Long> queue2;
    private long now;
    private long target;
    private int count = 0;

    TwinQueue(List<Long> list1, List<Long> list2, long sum1, long sum2) {
        queue1 = new LinkedList(list1);
        queue2 = new LinkedList(list2);
        now = sum1;
        target = (sum1 + sum2) / 2;
    }
    ...
}

큐 2개를 지닌 클래스를 생성하였다.
현재 queue1의 총 합과 목표로 하는 값을 설정하였다.

public int makeEqual() {
    while (target != now) {
        try {
            if (now < target) {
                long l = queue2.remove();
                queue1.add(l);
                now += l;
            } else if (now > target) {
                now -= queue1.remove();
            }
        } catch(Exception e) {
            return 1000000;
        }
        count++;
    }
    return count;
}

그 후 makeEqual을 통해 queue1을 늘리고 줄이며 목표값과 같아지는지 확인했다.
만약 같아졌다면 해당 목표치에 달성하기 위해 연산한 횟수를 return했다.
만약 queue1, queue2 내의 값이 모두 사라져 더 이상 연산할 수 없는 경우에는 백만을 return했다.

solution

long sum1 = Arrays.stream(queue1).asLongStream().sum();
long sum2 = Arrays.stream(queue2).asLongStream().sum();

if ((sum1 + sum2) % 2 == 1)
    return -1;

두 Array의 합을 각각 구했다. 만약 최종합이 짝수가 아니라면(절반으로 나누어떨어지지 않는다면) -1을 return했다.

List<Long> list1 = Arrays.stream(queue1).asLongStream().boxed().collect(Collectors.toList());
List<Long> list2 = Arrays.stream(queue2).asLongStream().boxed().collect(Collectors.toList());

TwinQueue twinQueue1 = new TwinQueue(list1, list2, sum1, sum2);
TwinQueue twinQueue2 = new TwinQueue(list2, list1, sum2, sum1);

두 Array를 List로 변경한 후 class 객체를 생성했다.

int result1 = twinQueue1.makeEqual();
int result2 = twinQueue2.makeEqual();
int result = Math.min(result1, result2);

생성된 class 객체에서 각각 목표값에 해당하는 횟수를 return받아 최솟값을 얻어냈다.

if (result == 1000000)
    return -1;

return result;

만약 최솟값이 백만이라면, 둘 다 계산할 수 없는 경우이니 -1을 return했다.
아니면 그냥 최솟값 return.

Python

두 리스트를 합친 큐를 만들고 연산을 했다.

풀이 코드

def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2:
        return -1
    
    want = (sum(queue1) + sum(queue2)) // 2
    queue = [queue1 + queue2, queue2 + queue1]
    answer = len(queue1) * 5
    
    for q in queue:
        head = 0
        tail = len(queue1)
        val = sum(q[head: tail])
        cnt = 0

        while head != tail and head < len(q) - 1:

            if val == want:
                answer = min(answer, cnt)
                break
            
            if val < want:
                val += q[tail]
                tail += 1
                tail %= len(q)
            
            else:
                val -= q[head]
                head += 1
                head %= len(q)
            
            cnt += 1
    
    return answer if answer != len(queue1) * 5 else -1

해석

if (sum(queue1) + sum(queue2)) % 2:
    return -1

모든 값의 합이 짝수가 아닌 경우 -1을 return.

want = (sum(queue1) + sum(queue2)) // 2
queue = [queue1 + queue2, queue2 + queue1]
answer = len(queue1) * 5

목표값을 정한 후 queue의 순서를 바꿔 합한 2개의 list를 생성했다.
또한 초기 결과값을 정상적인 계산 내에서 절대 도달할 수 없는 값으로 생성했다.

for q in queue:
    head = 0
    tail = len(queue1)
    val = sum(q[head: tail])
    cnt = 0
    
    while head != tail and head < len(q) - 1:
    
        if val == want:
            answer = min(answer, cnt)
            break
        
        if val < want:
            val += q[tail]
            tail += 1
            tail %= len(q)
        
        else:
            val -= q[head]
            head += 1
            head %= len(q)
        
        cnt += 1

리스트를 하나씩 가져와서 head와 tail을 설정하고, head부터 tail 직전값까지의 합이 목표값보다 크냐 작냐에 따라 head나 tail을 옮겼다.

return answer if answer != len(queue1) * 5 else -1

만약 결과값이 초기 결과값과 다르다면 그대로 return, 아닌 경우 -1을 return했다.

여담

다른 분들의 자바 풀이를 봤는데, 확실히 느낌이 달랐다. 이런 감성이 아닌가보다 ㅋㅋㅋㅋ..
그래도 클래스 만들어 푸니까 재밌더라. 앞으로도 이런 식으로 풀어볼까 고민.

그리고 문제 해석을 자바와 파이썬 둘 다 작성하니 시간이 너무 오래 걸린다.
모든 문제에 대해 이렇게 하면.. 한참 걸릴 것 같은데..
대충 넘어갈 부분은 넘기며 글을 써야겠다.