2022 KAKAO TECH INTERNSHIP 풀이

Level 1 - 성격 유형 검사하기 풀이
Level 2 - 두 큐 합 같게 만들기 풀이
Level 3 - 코딩 테스트 공부 풀이
Level 3 - 등산코스 정하기 풀이
Level 4 - 행렬과 연산 풀이

프로그래머스 - 두 큐 합 같게 만들기 링크
(2022.10.26 기준 Level 2)

문제

길이가 같은 두 큐가 있고 한 큐에서 원소를 pop하여 다른 큐에 pop한 원소를 insert하는 것을 작업 1회로 생각한다면, 두 큐의 합이 같게 하는 최소 작업 횟수

알고리즘

원소 합이 같게끔 두 큐 중 최적의 원소를 뽑아 작업해야 한다. 그때마다 상황보고 최적해를 찾아가는 그리디

풀이

이 문제는 심플하다. 두 큐 중 어떤 큐에서 뽑아서 다른 큐에 넣을지 그 방법만 생각해내면 그 작업 자체를 구현하면서 횟수를 세면 된다.

두 큐의 합이 같게 만들어야 한다.
그렇다면 합이 큰 쪽에서 뽑아야 할까? 작은 쪽에서 뽑아야 할까? 당연히 큰 쪽에서 뽑아서 작은 쪽으로 넘겨주는게 최대한 같게 만드는 방법이다.
여기서 제일 범하기 쉬운 실수는? 작업마다 sum 함수를 쓰는 것. 절대 안된다.
처음에 두 큐의 합을 각각 구해두고 작업마다 뽑은 원소를 각 합에 빼주고 더하고 하면 된다.

그리고 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우가 있다.
그래서 작업 횟수에는 제한을 둬야 한다.
난 처음엔 (큐의 길이 * 2)로 했지만 실패.

queue1 = [3, 3, 3, 3]
queue2 = [3, 3, 21, 3]

이 반례를 살펴보자. 답은 9이다. 큐의 길이 *2를 넘어가는 경우를 확인할 수 있다.
그래서 여유롭게 작업 횟수 제한을 큐의 길이 *4를 줬더니 전부 AC.

코드

from collections import deque

def solution(queue1, queue2):
    sum1 = sum(queue1) # queue1의 합
    sum2 = sum(queue2) # queue2의 합
    if sum1 == sum2: # 처음부터 같다면 0 반환
        return 0

    # 두 큐를 덱으로 만들어준다.
    queue1 = deque(queue1)
    queue2 = deque(queue2)

    # 작업 횟수 제한은 여유롭게 len(queue) * 4로 두자.
    for result in range(len(queue1) * 4):
        # 큰 쪽에서 작은 쪽으로 원소를 넘겨주자.
        if sum1 > sum2: 
            element = queue1.popleft()
            sum1 -= element
            queue2.append(element)
            sum2 += element
        else:
            element = queue2.popleft()
            sum2 -= element
            queue1.append(element)
            sum1 += element

        # 합이 같다면 횟수 반환 후 중단
        if sum1 == sum2:
            return result + 1

    # 횟수 제한을 넘겼다면 -1 반환
    return -1

여담

두 포인터로 풀려다가 흠.. 뭔가 반례가 잔뜩 생기겠다 싶어서 접고 그냥 심플하게 작업 자체를 구현했다.
반례가 없이 완벽하게 해내려는 마음. 이게 다 백준 때문이야.