Welcome to My IT World

코딩테스트 연습 - 두 큐 합 같게 만들기

문제요약

길이가 동일한 큐 2개가 주어짐

하나의 큐에서 추출해서 다른 큐에 삽입함 : FIFO 방식으로 진행

추출+삽입 = 1회

두 큐의 합이 같아질 수 있는 최소 횟수 return

만일, 불가능하면 -1 return

입력

1≤ 각 q의 길이 ≤ 3*10^5

1≤ q의 원소 ≤ 10^9

출력

return int

불가능하면, return -1

어떻게 풀까?

1. 일단, 입력 값의 범위를 봤을 때, O(n^2)는 불가능하고 O(nlogn) 정도까지는 가능
2. 제일 먼저 예외처리를 할 수 있는 건, 두 큐의 합이 짝수가 아닐 때! 큐의 합을 모두 더해서 짝수가 아니면 바로 return -1을 해주자!
3. 가장 간단하게 푸는 방법?
   while 문 돌리면서 각 큐의 합을 비교하고 큰 큐에서 값을 빼서 작은 큐에 넣어주는 것 반복 어차피 FIFO 방식이기 때문에, 결국 돌고 돌면서 크고 작음이 조율될 것!
   이때 문제는, 이게 얼마나 돌아야 return -1 판별이 가능한지임 사실 두 q 길이의 합 만큼 돌리면 원상복귀이기 때문에 더 이상 돌 필요가 없음! => 두 q 길이의 합은 2*3*10^5 로 충분히 가능!
4. 이 때, 주의할 점은 deque로 만들어주고 해야한다는 점! 배열에서 바로 pop(0)을 해주면, O(N)이 걸리기 때문(배열에서 앞에걸 빼면 뒤에 원소들도 다 자리이동을 시키기 때문에)에 시간초과가 남 ⇒ deque popleft() 이용 : O(1)

내 코드

다르게 푸는 방법?

투포인터 활용하기!

def solution(queue1, queue2):
    target = (sum(queue1) + sum(queue2)) // 2
    cur = sum(queue1)
    queue3 = queue1 + queue2 + queue1

    s = 0
    e = len(queue1) - 1
    answer = 0
    while True:
        if cur == target:
            return answer
        if cur < target:
            e += 1
            if e >= len(queue3):
                return -1
            cur += queue3[e]
        else:
            cur -= queue3[s]
            s += 1
        answer += 1

" 위 풀이코드 출처 : algorithm-ps/두 큐 합 같게 만들기.md at main · dali0202/algorithm-ps "  

위 코드에서 유심히 볼 점!

단순히 q1+q2로 합치지 않고 q1+q2+q1를 해준 점

아래와 같은 경우가 있을 수 있음