[2022 KAKAO TECH INTERNSHIP] Q2. 두 큐 합 같게 만들기 (C++, Python, Java)

문제 링크

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

 

예상 난이도

S2

 

알고리즘 분류

투 포인터 or 그리디

 

풀이 - 투 포인터

먼저 투 포인터 풀이를 살펴보겠습니다. 큐1은 (3, 2, 7, 2)이고 큐2는 (4, 6, 5, 1)인 상황에서 작업을 수행하는 상황인데 이걸 보면서 아주 중요한 관찰을 하나 할 수 있어야 합니다.

 

그건 바로 2n개의 원소를 일렬로 늘어놓으면 각 큐에 들어있는 원소가 연속한 구간에 위치한다는 사실입니다. 큐1에서 pop을 해 큐2를 주거나, 큐2에서 pop을 해 큐1을 주는 연산은 큐1과 큐2가 맞닿아있는 경계에서 원소를 넘겨주는 연산이기 때문에 그렇습니다.

 

그러면 우리는 임의의 연속한 구간을 잡아 해당 구간을 큐1으로 정할 경우 연산을 몇 번 해야하는지 계산 가능합니다.

 

그리고 우리는 각 지점을 큐1의 시작점으로 잡았을 때 연속된 구간의 합이 전체의 절반 이상이 되는 최초의 끝 점이 어디인지를 투 포인터로 총 O(N)에 구할 수 있습니다. (BOJ 1806) 투 포인터를 모르면 제 강의를 참고해보세요. 이렇게 구간을 정해놓고 나면 앞에서 본 것과 같이 연산을 몇 번 해야하는지 계산할 수 있습니다.

 

사실 잘 보면  명백히 답이 아닌 경우를 세는 것도 분명 있긴 합니다. 예를 들어서 지금 시작점이 6번째인 이 경우를 보면 사실 큐1의 시작점을 6까지 밀바에야 그냥 큐2의 시작점을 6으로 보내는게 더 낫다는 느낌이 옵니다. 하지만 그런 경우를 내가 예외처리를 하는 것 보다는 그런 예외처리에 뭔가 머리를 덜 쓸 수 있게 그냥 모든 경우를 다 보게끔 했습니다. 그래서 그냥 모든 지점이 큐1의 front가 될 수 있다고 생각을 하고 풀이를 작성했습니다.

 

코드(C++, 투 포인터)

 

코드(Python, 투 포인터)

 

코드(Java, 투 포인터)

 

풀이 - 그리디

두 번째는 그리디 풀이입니다. 저는 처음 문제를 풀 당시 2번 문제부터 투 포인터가 나오는건 좀 과하다고 생각해서 고민을 거듭하다가 그리디 풀이를 떠올렸는데, 핵심은 바로 저 2가지의 관찰입니다. 첫 번째로 각 큐에서 pop을 하는 횟수가 정해지면 pop을 하는 순서와 무관하게 각 큐에 들어가는 원소가 정해집니다. 두 번째로 현재 큐1의 원소 합이 더 크면 큐1에서 pop을 1번은 해야 합니다. 이 두 가지 사실을 종합하면 현재 큐1의 원소 합이 더 크면 큐1에서 언젠가 pop을 하게 되고, 또 pop을 하는 순서는 마음대로 정하면 되니 pop을 지금 바로 하면 됨을 알 수 있습니다. 즉 원소의 합이 더 큰 큐에서 pop을 하는걸 계속 반복하면 됩니다.

 

그리고 pop을 4n번 한 후에도 합이 같아지지 않았다면 적어도 어느 한 큐는 pop이 2n번 이루어지면서 처음 상태로 돌아왔으니 탐색을 종료할 수 있습니다.

 

코드(C++, 그리디)

 

코드(Python, 그리디)

 

코드(Java, 그리디)