[프로그래머스] 두 큐 합 같게 만들기 풀이 (2022 카카오 인턴십)

| |
프로그래머스 - 두 큐 합 같게 만들기 C++ 풀이 (2022 카카오 인턴십 코딩테스트 기출)


문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

1
2
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다. 따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.


제한사항

  • 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
  • 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
  • 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.


풀이

2022 카카오 인턴십 코딩테스트 2번 문제로, 오히려 대부분 1번 문제보다 해결 시간이 적었을 것으로 예상되는 문제였습니다.

굉장히 간단한 시뮬레이션 문제로, 문제에서 제시된 그대로 구현하면 되는 문제입니다. 두 큐 합이 아직 같지 않다면, 유일하게 할 수 있는 행동은 합이 더 작은 큐에서 합이 큰 큐로 push하는 것 뿐입니다.

생각해야할 것은 이 시뮬레이션을 얼마나 오래 실행할 것인가 입니다. 언젠가 두 큐의 합이 같아진다면 다행이지만, 그렇지 않은 입력이 주어진다면 무한 루프를 돌게 되기 때문입니다. 과연 언제까지 돌아야 모든 경우의 수를 완전 탐색했다고 단정할 수 있을까요?

두 큐의 상태가 처음과 같아지면 더 이상 진행할 이유가 없다

모든 경우의 수를 완전히 돌았다면, 언젠가는 두 큐의 상태가 처음으로 돌아와 다시 첫 번째 경우의 수부터 탐색할 것입니다. 그런데 두 큐의 상태가 처음으로 돌아오는데 필요한 작업 수행의 횟수는 정해져 있습니다. 두 큐의 숫자들을 모두 바꿔치기 한다고 가정했을 때 필요한 작업의 수는 (queue1 원소의 갯수) + (queue2 원소의 갯수)임은 쉽게 알 수 있습니다. 이때 두 큐의 숫자들을 다시 한 번 모두 바꿔치기 하면 두 큐의 상태는 처음으로 돌아가게 됩니다. 따라서 모든 경우의 수를 돌아보는데 필요한 작업 수는 모든 원소 바꿔치기를 2번하는 연산 수이므로 2 * ((queue1 원소의 갯수) + (queue2 원소의 갯수)) 입니다.

또한, C++의 경우 문제에서 주어진 것과 같이 합 연산 도중 int 범위를 넘어갈 수 있으므로 long long 자료형을 이용해주어야 하는 점도 유의합시다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    long long sum1 = 0, sum2 = 0;
    queue<int> q1, q2;
    
    for(int i : queue1) { q1.push(i); sum1 += i; }
    for(int i : queue2) { q2.push(i); sum2 += i; }
    
    while(sum1 != sum2 && answer < 2 * (q1.size() + q2.size())) {
        if(sum1 > sum2) {
            q2.push(q1.front());
            sum1 -= q1.front();
            sum2 += q1.front();
            q1.pop();
        }
        else {
            q1.push(q2.front());
            sum1 += q2.front();
            sum2 -= q2.front();
            q2.pop();
        }
        answer++;
    }
    
    if(sum1 != sum2) answer = -1;
    
    return answer;
}
0%