프로그래머스_두 큐 합 같게 만들기_level2(python)

※ 접근법

 두 큐 합을 같게 만들기 위한 방법은 여러가지가 있고 최소 횟수를 구해야하니 모든 경우의 수를 파악해야 한다고 생각했다. 하지만 제한사항에서 두 큐의 리스트의 길이가 최대 300,000인 것을 보고 완전탐색을 하면 안 된 다는 것을 느꼈다.

 

※ 풀이

 1. 두 큐 리스트의 합을 비교해 큰 쪽에서 팝을 하고 작은 쪽에다가 append를 해준다.

2. 두 큐 값이 같아지거나, 한 쪽 큐가 비워지거나, 큐 하나 길이에 * 4만큼 반복을 했으면 무한루프를 끝내준다.

3. 2번 조건에 들어가기 전 까지 1번 조건을 반복해준다.

 

def solution(queue1, queue2):
    count = 0
    one_sum = sum(queue1)
    two_sum = sum(queue2)
    total = one_sum + two_sum
    que1 = deque(queue1)
    que2 = deque(queue2)    
    if total % 2 == 1:
        return -1
    while True:
        if one_sum == two_sum:
            return count
        if len(que1) == 0 or len(que2) == 0 or count == (len(que1) + len(que2)) * 2:
            return -1
        count += 1
        if one_sum > two_sum:
            temp = que1.popleft()
            que2.append(temp)
            one_sum -= temp
            two_sum += temp
        else:
            temp = que2.popleft()
            que1.append(temp)
            two_sum -= temp
            one_sum += temp

 

※ 회고

 무한루프를 탈출하는 조건 중에 처음에 count가 두 큐 길이와 같았으면 -1을 리턴을 하게 해줬다. 왜냐하면 큐는 선입선출이라는 특징 때문에 두 큐 길이만큼만 반복하면 두 큐의 들어있던 숫자가 완전히 뒤바뀌게 된다.  근데 1번이 통과가 되지 않았고 반례가 있겠다 싶어서 범위를 *4로 늘려줬더니 통과가 됐다. 추측해서 푼 거였기 때문에 이유를 알라고 구글링을 해봤지만 사람들도 저 범위를 추측해서 풀었다. 처음에는 '추측을 해서 푸는 문제가 어디있어'라고 생각했지만 그래도 이런 문제들을 풀어보는것도 나쁘지는 않은 것 같다.