프로그래머스 | 두 큐 합 같게 만들기 [파이썬 python]

프로그래머스

 

단순한 큐를 이용한 문제라 생각하고 접근했으나 조건들로 인해 실패했던 과정을 하나하나 코드와 함께 작성했다.

발생할 수 있는 모든 경우를 겪고 정리했으니 다들 여기서 해답을 찾으시길 바랍니다!

 

시행착오 1

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    answer = 0
    
    # 원소는 정수이므로 두 큐의 합이 홀수이면 어떻게 해도 각 큐의 합을 정수로 같게 만들 수 없음(ex. 17 -> 8.5)
    if (sum(queue1) + sum(queue2)) % 2 == 1:
        return -1
    
    while sum(queue1) != sum(queue2):
        # 불가능한 경우
        if not queue1 or not queue2:
            return -1
        
        # 합이 큰 쪽에서 원소를 추출하여 다른 쪽에 추출한 원소 추가
        if queue1 and queue2 and sum(queue1) < sum(queue2):
            queue1.append(queue2.popleft())
            answer += 1
        elif queue1 and queue2 and sum(queue1) > sum(queue2):
            queue2.append(queue1.popleft())
            answer += 1
            
    return answer

문제에서 제공된 예시를 통해 합이 큰 쪽에서 원소를 추출해 다른 쪽에 추가해 주면 된다는 것을 알 수 있었다.

이를 바탕으로 코드를 작성했으나 결과는 처참하게도 시간 초과를 만나게 되었다.

 

코드를 들여다보며 시간 초과가 발생하는 부분에 대해 생각을 해보니 queue의 길이가 길면 길 수록 sum() 연산에 소요되는 시간이 길어질 것이라고 생각하게 되어 각 큐의 합을 하나의 변수로 만들어 가감해 주는 방향으로 코드를 수정했다.

 

시행착오 3

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2) # 각 큐의 합
    answer = 0
    
    # 원소는 정수이므로 두 큐의 합이 홀수이면 어떻게 해도 각 큐의 합을 정수로 같게 만들 수 없음(ex. 17 -> 8.5)
    if (sum1 + sum2) % 2 == 1:
        return -1
    
    while sum1 != sum2:
        # 불가능한 경우
        if not queue1 or not queue2:
            return -1
        
        # 합이 큰 쪽에서 원소를 추출하여 다른 쪽에 추출한 원소 추가
        if sum1 < sum2:
            i = queue2.popleft()
            queue1.append(i)
            sum2 -= i
            sum1 += i
            answer += 1
            
        elif sum1 > sum2:
            i = queue1.popleft()
            queue2.append(i)
            sum1 -= i
            sum2 += i
            answer += 1
            
    return answer

그 결과, 대부분의 테스트 케이스에서 시간 초과를 피할 수 있었지만 11, 28번 두 테스트 케이스에서 여전히 시간 초과가 발생했다.

sum이 아닌 부분에서 시간 초과가 발생할 수 있는 원인은 while문에서 무한 루프가 발생하는 경우뿐이었다.

분명히 최대 반복 횟수가 존재하고 그 횟수를 넘어섰기 때문에 무한 루프가 발생하는 것이라고 생각했다.

 

시행착오 4

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2) # 각 큐의 합
    count = len(queue1) + len(queue2)
    answer = 0
    
    # 원소는 정수이므로 두 큐의 합이 홀수이면 어떻게 해도 각 큐의 합을 정수로 같게 만들 수 없음(ex. 17 -> 8.5)
    if (sum1 + sum2) % 2 == 1:
        return -1
    
    while sum1 != sum2:
        # 한 쪽 큐가 비는 경우(불가능)
        if not queue1 or not queue2:
            return -1
        
        if count > 0:
            # 합이 큰 쪽에서 원소를 추출하여 다른 쪽에 추출한 원소 추가
            if sum1 < sum2:
                i = queue2.popleft()
                queue1.append(i)
                sum2 -= i
                sum1 += i
                count -= 1
                answer += 1

            elif sum1 > sum2:
                i = queue1.popleft()
                queue2.append(i)
                sum1 -= i
                sum2 += i
                count -= 1
                answer += 1
        else:
            return -1
            
    return answer

그래서 최대 반복 횟수로 count 변수를 만들어 주었고, count는 두 큐의 길이의 합(=원소의 총 개수)으로 설정하고 제출했다.

하지만 돌아온 결과는 색달랐다.

위에서 발생했던 11, 28번 테스트 케이스는 통과가 되었는데, 이전까지는 통과였던 1번 테스트 케이스가 갑자기 실패로 바뀐 것이다.

최대 반복 횟수라는 조건을 걸어주기 전까지는 통과했던 1번 테스트 케이스가 갑자기 조건을 걸어주면서 실패로 변했으니 분명 1번 테스트 케이스는 len(queue1) + len(queue2) 이상의 횟수가 필요한 것임을 알 수 있다.

 

정답 코드

from collections import deque

def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2) # 각 큐의 합
    count = len(queue1) + len(queue2) + 2 # 최대 이동 횟수
    answer = 0
    
    # 원소는 정수이므로 두 큐의 합이 홀수이면 어떻게 해도 각 큐의 합을 정수로 같게 만들 수 없음(ex.17 -> 8.5)
    if (sum1 + sum2) % 2 == 1:
        return -1
    
    # 두 큐의 합이 같아질 때까지 반복
    while sum1 != sum2:        
        if count > 0:
            # 합이 큰 쪽에서 원소를 추출하여 다른 쪽에 추출한 원소 추가
            if sum1 < sum2:
                i = queue2.popleft()
                queue1.append(i)
                sum2 -= i
                sum1 += i
                count -= 1
                answer += 1

            elif sum1 > sum2:
                i = queue1.popleft()
                queue2.append(i)
                sum1 -= i
                sum2 += i
                count -= 1
                answer += 1
        
        # 최대 이동 횟수 초과시 -1 리턴
        else:
            return -1
            
    return answer

최대 이동 횟수를 찾기 위해 다른 테스트케이스들을 찾아보니 한쪽으로 값이 몰린 경우를 살펴보면 답을 찾을 수 있었다.

예를 들어, queue1 = [1, 1, 1, 1, 1], queue2 = [1, 1, 1, 9, 1]과 같은 경우엔 총 12번의 작업이 필요하고, queue1=[1, 1, 1, 8, 10, 9], queue2=[1, 1, 1, 1, 1, 1]인 경우에는 총 14번의 작업이 필요하다.

queue1과 queue2의 길이는 같으므로 여기서 최대 이동 횟수는 len(queue1) * 2 + 2가 되는 것을 알 수 있고, 이 값을 count로 설정해 주면 모든 테스트 케이스에서 통과된다.

그리고 while문 전의 원소의 총합이 홀수인지 확인하는 if문과 while문 시작 후 queue가 존재하는지 확인하는 if문은 역할이 같아 둘 중 하나는 제거해 줘도 코드 실행에는 문제가 없음을 확인했다.