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

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

프로그래머스

나의 풀이 - 실패(60점)

from collections import deque

def solution(queue1, queue2):
    answer = 0
    dq1 = deque(queue1)
    dq2 = deque(queue2)
    targetValue = (sum(dq1)+sum(dq2))//2
    
    for i in range(len(dq1)+len(dq2)):
        if sum(dq1) < targetValue:
            dq1.append(dq2.popleft())
            answer += 1
        if sum(dq1) > targetValue:
            dq1.popleft()
            answer += 1
        if sum(dq1) == targetValue:
            return answer
    answer = -1
    return answer

• 반복문 안에서 계속 sum을 해줘서 시간초과가 났다.

나의풀이 - 실패 (98점)

from collections import deque

def solution(queue1, queue2):
    answer = 0
    dq1, dq2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(dq1), sum(dq2)
    
    if (sum1+sum2)%2 != 0:
        return -1
    
    for i in range(len(dq1)+len(dq2)):
        if sum1 < sum2:
            pl2 = dq2.popleft()
            dq1.append(pl2)
            sum1 += pl2
            sum2 -= pl2
        elif sum1 > sum2:
            pl1 = dq1.popleft()
            dq2.append(pl1)
            sum1 -= pl1
            sum2 += pl1
        else:
            return answer
        answer += 1
    return -1

• sum은 위에서 한번만 해주고 그때 그때 더하고 빼주는 로직으로 바꿨더니 시간초과는 사라졌다.
• 하지만 range 범위가 잘못되어 테스트케이스를 하나 통과하지 못했다.

나의풀이 - 성공

from collections import deque

def solution(queue1, queue2):
    answer = 0
    dq1, dq2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(dq1), sum(dq2)
    
    if (sum1+sum2)%2 != 0:
        return -1
    
    for i in range(len(dq1)*3):
        if sum1 < sum2:
            pl2 = dq2.popleft()
            dq1.append(pl2)
            sum1 += pl2
            sum2 -= pl2
        elif sum1 > sum2:
            pl1 = dq1.popleft()
            dq2.append(pl1)
            sum1 -= pl1
            sum2 += pl1
        else:
            return answer
        answer += 1
    return -1

• 결국 실패하는 테스트케이스를 찾지 못해 검색을 했다.
• 큐 크기의 2배 만큼만 실행하면 된다고 생각했는데, 아래와 같은 케이스로 인해 3배로 실행해야 했다.

💡 큐 크기 * 3 만큼의 반복을 실행하는 이유!

• 반례를 통해서 설명할 수 있다.
• 입력값을 받은 queue1 과 queue2 의 값이 각각 [1, 1, 1, 8, 10, 9] 와 [1, 1, 1, 1, 1, 1] 이다.
• 이 경우는 총 14번의 원소 이동이 발생해야 두 큐 원소의 합이 같아질 수 있다.
  

  

• queue1 의 크기 6에 2를 곱한 12 만큼의 원소 이동을 진행한 후 프로그램이 종료된다면 위와 같은 경우는 답을 찾지 못하게 된다.
• 최악의 경우에 대한 반례를 찾지는 못했지만 큐 크기 * 3 만큼의 반복을 진행한다면 모든 경우의 수를 확인할 수 있을 것이라고 개인적인 뇌피셜로 조심스럽게 추측하였다.

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EB%91%90-%ED%81%90-%ED%95%A9-%EA%B0%99%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Python