2022 KAKAO TECH INTERNSHIP > 두 큐 합 같게 만들기

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

두 큐의 합을 같게 하는 문제이다.

이를 위해서는 총합을 관리해줄 필요가 있으므로 총합을 초기화 해준 다음 더 큰 쪽의 top 값을 작은 쪽으로 옮겨주는 것을 반복하도록 하였다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    int q1 = 0, q2 = 0;
    for(int q : queue1) q1+=q;
    for(int q : queue2) q2+=q;
    while(q1!=q2){
        if(q1>q2){
            q2+=queue1.front();
            q1-=queue1.front();
            queue2.push_back(queue1.front());
            queue1.erase(queue1.begin());
        }
        else if(q1<q2){
            q1+=queue2.front();
            q2-=queue2.front();
            queue1.push_back(queue2.front());
            queue2.erase(queue2.begin());
        }
        answer++;
    }
    return answer;
}

 

위 코드는 두 가지 문제점이 있었다.

불가능한 경우의 예외처리와 자료구조로 벡터를 사용하여 top을 제거하는데 있어 시간 복잡도가 높다는 것이다.

 

예외처리는 쉽게 처리하였지만 시간 복잡도 문제가 해결되지 않아 라이브러리를 추가하여 큐를 사용하기로 하였다.

 

아래가 해당 코드이다.

#include <queue>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    queue<int> q1, q2;
    long long sum1 = 0, sum2 = 0;
    
    for (int num : queue1) {
        q1.push(num);
        sum1 += num;
    }
    
    for (int num : queue2) {
        q2.push(num);
        sum2 += num;
    }
    
    int max_operations = queue1.size() * 3;  // 최대 반복 횟수 설정
    int operations = 0;
    
    while (sum1 != sum2) {
        if (operations >= max_operations) return -1;  // 무한 루프 방지
        
        if (sum1 > sum2) {
            int move = q1.front();
            q1.pop();
            q2.push(move);
            sum1 -= move;
            sum2 += move;
        } else {
            int move = q2.front();
            q2.pop();
            q1.push(move);
            sum2 -= move;
            sum1 += move;
        }
        operations++;
    }
    
    return operations;
}

초기화 하는 과정에서 자료구조를 큐로 바꾸어주고 모든 원소가 이동한 경우를 MAX 이동횟수로 두어 해당 시점에 도달한 경우에도 완성되지 않은 경우 불가능하다 두었다.