[프로그래머스] Lv2. 두 큐 합 같게 만들기(2022 카카오 공채)

문제

풀이

두 개의 큐는 길이가 최대 30만이기 때문에 실제로 pop, append를 사용하면 시간초과가 발생한다.

두 개의 큐를 연결해서 하나의 배열로 만든 다음에 투 포인터 방식으로 큐를 구현했다. i는 첫 번째 큐(queue1)의 가장 첫 번째 원소, j는 두 번째 큐(queue2)의 첫 번째 원소라고 했을 때, queue1의 합이 구하려는 목표치의 값(target)보다 작다면 queue2의 첫 번째 원소를 추가하고, j의 값을 증가시킨다. 반대로 target보다 값이 크다면 갖고 있는 첫 번째 원소를 제거하고 i를 증가시킨다.

불가능한 경우는 인덱스 값이 배열을 한 바퀴 돌아도 값을 찾을 수 없는 경우이다.

[1, 2, 9, 4]
[1, 1, 2, 2]

위의 경우 j의 값이 연결된 하나의 배열의 가장 끝 값을 넘어 다시 첫 번째 원소(queue1의 첫 번째 원소, i가 시작되는 지점)로 되돌아올 수 있다. 즉 여기서 j의 값은 순환큐처럼 배열을 한바퀴 돌아 다시 처음부터 시작될 수 있도록 구현되어야 한다. 무한으로 같은 탐색하지 않게 하기 위해 한 바퀴를 전부 돌면 종료될 수 있도록 while문의 조건문을 작성했다

def solution(queue1, queue2):
	# 두 개의 큐를 하나의 큐(Q)로 연결
    Q = queue1 + queue2
    Q1 = sum(queue1)
    
    # 합이 홀수인 경우는 볼가
    if sum(Q) % 2:
        return -1
    
    target = sum(Q)//2
    l = len(queue1)
    i, j = 0, l
    # l은 작은 큐의 길이이다. 2*l은 Q의 길이
    while i < 2*l-1 and j < 4*l:
    	# 타겟 목표에 도달하면 현재까지 이동한 거리를 인덱스 값을 통해 반환
        # i는 시작이 0이므로 그냥 반환
        # j는 시작이 l이었으므로 반환할 때는 l만큼 빼줘야 실제 이동된 순수 거리 값만 반환
        if Q1 == target:
            return i+j-l
        elif Q1 < target:
            Q1 += Q[j%(2*l)] # 순환 큐 형태
            j += 1
        elif Q1 > target:
            Q1 -= Q[i%(2*l)]
            i += 1
    return -1