[프로그래머스] 두 큐 합 같게 만들기 (Python)

문제 요약

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

 

두 개의 큐가 있는데 큐1의 가장 왼쪽 원소를 pop하면 큐2의 끝에 삽입된다.

이 과정을 반복하면서 두 큐의 원소의 합이 같도록 해야한다.

이때 합이 같아지기 위한 취소 횟수를 구하는 문제이다.

원소 합을 같게 만드는게 불가능하다면 -1을 반환한다.

 

첫번째 풀이

먼저 큐의 합이 같아지기 위해서는 무조건 합이 큰 큐에서 popleft를 해야한다고 생각했다.

따라서 큐의 합을 비교한 후 큰 값을 가지는 큐에서 popleft, 나머지 큐에서 append를 해주었다.

 

이 과정을 반복했을 때 합이 같아지게 되면 총 popleft+append한 횟수를 반환하도록 했다.

 

하나의 큐에 원소가 하나가 남았을 때, 남은 원소의 값이 다른 큐의 합보다 크면 -1을 반환하는 것으로 설정했다.

 

이렇게 풀었을 때 시간초과가 났다.

from collections import deque


def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)

    sum1 = sum(queue1)
    sum2 = sum(queue2)

    # 두 수의 합이 홀수일 때
    if (sum1 + sum2) % 2 != 0:
        return -1

    cnt = 0
    while True:
        if (len(queue1) == 1 and sum1 > sum2) or (len(queue2) == 1 and sum1 < sum2):
            return -1

        if sum1 > sum2:
            num = queue1.popleft()
            queue2.append(num)
            sum1 -= num
            sum2 += num
            cnt += 1
        elif sum1 < sum2:
            num = queue2.popleft()
            queue1.append(num)
            sum1 += num
            sum2 -= num
            cnt += 1
        else:
            return cnt

 

두번째 풀이

시간초과의 원인을 각 큐의 합을 매번 더하는 것이라고 판단하여 더하는 과정을 없애 보기로 했다.

두 큐를 하나의 큐로 묶고 idx1, idx2를 통해 각 큐의 시작점만 옮기는 방식으로 바꿨다.

 

두 큐의 합도 dif 변수를 통해 합의 차만 표시해주었다.

큐1에서 원소가 빠지고 큐2에 원소가 추가되면 두 큐의 합의 차는 (원소값)*2만큼 늘어난다.

dif -= queue[idx]*2

그리고 다시 각 큐의 시작점을 설정해주었다.

get_idx함수를 통해서 인덱스값이 큐의 길이를 넘어가도 다시 앞으로 보낼 수 있도록 했다.

idx = get_idx(idx + 1)

그런데 이 방식도 역시 시간초과가 났다.

 

초반에 접근부터 뒤집어야 하나 싶다..

조금 더 고민해보겠다.

from collections import deque


def solution(queue1, queue2):
    def get_idx(idx):
        if idx == len(queue):
            return 0
        else:
            return idx

    queue = deque(queue1 + queue2)

    idx1 = 0
    idx2 = len(queue1)

    dif=sum(queue1)-sum(queue2)

    # # 두 수의 합이 홀수일 때
    # if (sum1 + sum2) % 2 != 0:
    #     return -1

    cnt = 0
    while True:
        if dif>0:
            if idx2-idx1==1 or idx2-idx1+len(queue)==1:
                return -1

            dif -= queue[idx1]*2
            idx1 = get_idx(idx1 + 1)
        elif dif<0:
            if idx1-idx2==1 or idx1-idx2+len(queue)==1:
                return -1

            dif -= queue[idx2]*2
            idx2 = get_idx(idx2 + 1)
        else:
            return cnt

        cnt+=1

 

 

코드

찾아보니 sum을 사용하는 것이 문제가 아니라 -1를 반환하는 기준이 틀렸다. 

queue가 자기 자신이 될 때를 기준으로 -1을 반환해주었더니 해결할 수 있었다. 

from collections import deque

def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    
    qsum1 = sum(queue1)
    qsum2 = sum(queue2)
    limit = len(queue1) * 3
    cnt = 0
    while True:
        if cnt == limit:
            return -1
        if qsum1 > qsum2:
            tmp = queue1.popleft()
            qsum1 -= tmp
            qsum2 += tmp
            queue2.append(tmp)
        elif qsum1 < qsum2:
            tmp = queue2.popleft()
            qsum2 -= tmp
            qsum1 += tmp
            queue1.append(tmp)
        else:
            return cnt
        cnt += 1
    return -1