프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/118667

⌛ 56분

[나의 풀이]

from collections import deque

def solution(queue1, queue2):
    answer = -2
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    hap1 = sum(queue1)
    hap2 = sum(queue2)
    chance = 0
    max_chance = len(queue1)*3
    isFind = False

    while chance<max_chance:
        
        if hap1>hap2:
            v1 = queue1.popleft()
            queue2.append(v1)
            hap1 -= v1
            hap2 += v1
        elif hap1<hap2:
            v2 = queue2.popleft()
            queue1.append(v2)
            hap2 -= v2
            hap1 += v2
        else:
            isFind = True
            break
        chance += 1
    if isFind:
        return chance
    else:
        return -1

크기가 동일한 두 큐(queue1, queue2)가 주어지고 (1)queue1의 요소를 pop하여 queue2에 insert하거나, (2)queue2의 요소를 pop하여 queue1에 insert하여 각 큐들의 합을 같게하는 insert(pop) 최소 횟수를 구하는 문제입니다.

먼저 리스트로 입력되는 두 큐(queue1,queue2)를 deque()를 활용하여 Queue자료구조로 바꾸어주었습니다.

이후 각 큐의 합(hap1, hap2)을 미리 정의해줍니다. 이는 문제에서 정의한 큐의 최대 크기(300000)일 때를 기준으로 queue에 새로운 요소가 추가된어 합을 구해야한다면, 반복문이 실행될 때마다 최악의 경우 300000개를 sum()하여 합을 확인해야하기 때문에 시간 초과가 발생할 수 있기 때문입니다.

다음으로 현재 상태의 queue1의 합(hap1)과 queue2의 합(hap2)를 비교하여 hap1이 hap2보다 크다면 queue1의 요소를 queue2에 insert하고 그 반대라면 queue2의 요소를 queue1에 insert하여 hap1이 hap2와 같을 때까지 반복하는 방식입니다.

단, 큐 구조이므로 insert-pop을 계속 반복한다면 처음 queue1, queue2의 형태로 돌아오게 되므로 max_chance(처음 상태까지 돌아가는 횟수)를 정의하여 제한을 두어 두 큐가 같아질 수 없다면 -1를 반환합니다.

[다른 사람의 풀이]

def solution(queue1, queue2):
    _sum = (sum(queue1) + sum(queue2)) // 2
    
    if (max(queue1 + queue2) > _sum) : return -1
    
    answer, start1, start2 = 0, 0, 0
    end1, end2 = len(queue1) - 1, len(queue1) - 1
    lst1 = queue1 + queue2 + queue1
    lst2 = queue2 + queue1 + queue2
    sum1, sum2 = sum(queue1), sum(queue2)
    
    while sum1 != _sum and sum2 != _sum :

        if sum1 < _sum :
            end1 += 1
            if end1 == len(lst1) : return -1
            sum1 += lst1[end1]
        else :
            sum1 -= lst1[start1]
            start1 += 1
        
        if sum2 < _sum :
            end2 += 1
            if end2 == len(lst2) : return -1
            sum2 += lst2[end2]
        else :
            sum2 -= lst2[start2]
            start2 += 1
        answer += 1
    return answer

투 포인터 알고리즘을 활용한 풀이입니다.

Queue구조로 변환하여 popleft(), append()하는 방식이 아니라, 각 큐별로 다른 큐를 앞/뒤로 확장하여 투 포인터의 인덱스를 통해 범위를 규정하는 방식입니다.

예를 들어 queue1을 기준으로 앞/뒤로 queue2의 요소를 더하는 구조에서, popleft()해야한다면 start 인덱스를 더하며 append()해야한다면 end 인덱스를 더하여 범위를 정하고 합을 확인할 수 있었습니다.

각 큐의 합들(sum1, sum2)을 미리 규정하고 새로 추가/삭제되는 요소만 연산(+/-)하여 반복문 실행 시마다 sum()하지 않도록 한 부분은 '나의 풀이'와 같았습니다.

감사합니다.