Python/Algorithm

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

언킴 2023. 9. 5. 12:12
반응형

해당 문제는 2022 KAKAO TECH INTERNSHIP에 출제된 문제다. 프로그래머스 기준 Level 2에 해당한다. Queue를 통해 푸는 문제로 collections 내 queue를 사용하면 된다. 

from collections import deque
def solution(queue1, queue2):
    answer = 0 
    q1 = deque(queue1)
    q2 = deque(queue2)
    _max = (len(queue1)) * 3
    t1 = sum(q1)
    t2 = sum(q2)
    total = t1 + t2 
    
    if total % 2 != 0:
        return -1

queue에서는 popleft라는 함수가 있어서, 왼쪽에 있는 값을 빼는 형태로 진행한다. 문제에서 조건 자체가 왼쪽에 있는 값을 차례대로 pop하는 것이기 때문에, 위와 같이 queue로 받아온다. _max는 반복 횟수가 너무 많아지는 것을 처리하기 위함이다. 

 

만약 queue1과 queue2의 합이 2로 나누어 떨어지지 않는다면, 해당 문제를 풀 수 없기 때문에 미리 return -1을 해주는 형태로 처리가 가능하다. 

    while 1:
        if t1 > t2:
            src = q1.popleft()
            q2.append(src)
            t1 -= src
            t2 += src
            answer += 1
        
        elif t1 < t2:
            src = q2.popleft()
            q1.append(src)
            t1 += src
            t2 -= src
            answer += 1
        
        else:
            break 
        
        if answer == _max:
            answer = -1 
            break 
    
    return answer

다음으로는 queue1의 합과 queue2의 합을 비교해 합산이 더 큰 값을 기준으로 값을 빼주어 작은 queue에 더해주는 형태로 처리할 수 있다. 그러고 pop, insert를 하나의 횟수로 보기 때문에 answer += 1로 처리하는 것을 확인할 수 있다. 마지막 if 문에서 너무 많은 횟수를 반복하지 않도록 break를 걸어주면 쉽게 해결이 가능하다. 전체 코드는 아래와 같다. 

 

from collections import deque
def solution(queue1, queue2):
    answer = 0 
    q1 = deque(queue1)
    q2 = deque(queue2)
    _max = (len(queue1)) * 3
    t1 = sum(q1)
    t2 = sum(q2)
    total = t1 + t2 
    
    if total % 2 != 0:
        return -1
    
    while 1:
        if t1 > t2:
            src = q1.popleft()
            q2.append(src)
            t1 -= src
            t2 += src
            answer += 1
        
        elif t1 < t2:
            src = q2.popleft()
            q1.append(src)
            t1 += src
            t2 -= src
            answer += 1
        
        else:
            break 
        
        if answer == _max:
            answer = -1 
            break 
    
    return answer