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

문제 링크

프로그래머스

문제 풀이

투포인터에 관한 문제이다. 합계를 미리 계산해두고, 조건에 따라 값을 추가하거나 빼는 형식으로 반복문을 돌려주었다.

이 문제의 제목에서부터 큐를 사용해야한다고 생각이 들겠지만, 사실 사용하지 않아도 된다. 오히려 파이썬에서는 deque를 사용하는 것이 리스트 사용보다 더 안좋을수도 있다.

이 문제를 풀기 위해서 일단, 기본적으로 확인해볼 것은 제한사항이다. 두 queue의 길이가 최장 300000까지 될 수 있다고 하니, 시간복잡도에 대해 조금 더 신경써주어야 한다. 그 외의 사항은 파이썬에서는 크게 고려하지 않아도 좋다.

먼저, 이 문제를 투 포인터로 푸는 이유가 시간복잡도를 고려해야하기 때문이다. 만약, 300000 길이의 큐의 합을 구하기 위해서는 sum 함수의 경우 O(N)의 시간복잡도가 소요될 것이다. 여기서, 큐가 변화함에 따라 sum함수를 사용해서 합계를 다시 구한다고 생각해보면, 시간복잡도는 굉장히 커질 것이다.

그러므로 맨 처음에 최댓값을 구한 이후부터는 값이 하나씩 더해지고 빼질때마다 최댓값에서 그 수를 더해주거나 빼주면 되므로 이때의 시간복잡도는 O(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