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

[LV2] 두 큐 합 같게 만들기 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다 www.programmers.co.kr

 

문제 해설

이번 문제는 문제에서 설명하는 것처럼 큐를 사용해서 서로의 크기가 같아질 때까지 삽입과 추출하는 반복문을 돌려서 두 큐의 합이 같아질지 판별하면 되는데 여기서 중요한 점은 판별을 할 때의 범위를 정해야 한다. 이때 이 범위는 큐의 길이의 3배만큼 돌리게 되면 모든 경우의 수를 반복해볼 수 있기 때문에 3*len(que1)의 범위로 판별하면 된다.

 

from collections import deque

def solution(queue1, queue2):
    answer = 0
    chk=0 # 각각의 큐의 합이 같은지 판별하는 변수 0이면 불가능하고 1이면 가능하다
    sum1=sum(queue1) #첫번째 큐의 합
    sum2=sum(queue2) #두번째 큐의 합
    que1,que2=deque(queue1),deque(queue2) #두 리스트 큐로 변환
    
    for _ in range(3*len(queue1)):
        if sum1<sum2: #만약 첫번째 큐의 합이 두번쨰 큐의 합보다 적다면 2번큐에 원소를 1번큐로 이동
            tmp=que2.popleft()
            sum1+=tmp
            sum2-=tmp
            que1.append(tmp)
        elif sum1==sum2: #만약 두 합이 같다면 반복문 탈출
            chk=1
            break
        else: #1번큐의 합이 2번큐의 합보다 크다면 1번큐의 원소를 2번큐로 이동
            tmp=que1.popleft()
            sum1-=tmp
            sum2+=tmp
            que2.append(tmp)
        answer+=1 #움직인 횟수 +1
    if chk==1: #만약 서로가 같은 경우가 생긴다면 움직인 횟수 출력
        return answer
    else: #불가능하다 하면 -1 리턴 
        return -1

 

KEY POINT

• deque를 사용하여 리스트를 que형태로 변환 시킨다
• 모든 경우의 수를 확인해봐야 하기 때문에 전체 길이*3의 반복을 한다
• sum을 지속적으로 사용할 시 시간 초과가 발생할 수 있기 때문에 +,-연산을 사용한다