본문 바로가기

Algorithm/Programmers

[Programmers] 두 큐 합 같게 만들기 (C++)

728x90
반응형

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    long long quesum1 = 0, quesum2 = 0;
    queue<int> q1; queue<int> q2;
    for(int i = 0; i < queue1.size(); i++){
        quesum1 += queue1[i];
        q1.push(queue1[i]);
    }
    for(int i = 0; i < queue2.size(); i++){
        quesum2 += queue2[i];
        q2.push(queue2[i]);
    }
    
    if((quesum1 + quesum2) % 2 != 0) return -1;
    
    int n = 3 * quesum1;
    
    while(n--){
        if(quesum1 > quesum2){
            int x = q1.front();
            quesum2 += x;
            quesum1 -= x;
            q2.push(x);
            q1.pop();
        } else if(quesum1 < quesum2){
            int x = q2.front();
            quesum1 += x;
            quesum2 -= x;
            q1.push(x);
            q2.pop();
        } else{
            return answer;
        }
        answer++;
    }
    return -1;
}

 

vector의 erase로 맨 앞 원소를 제거하는 것은 시간복잡도가 O(n)으로 느리기 때문에 queue로 옮겨서 풀었다.

최적의 해를 찾는 방법은 두 큐의 합이 같아질 때까지 원소의 합이 높은 큐에서 낮은 큐로 원소를 옮기는 것이다.

모든 원소들의 합이 홀수인 경우는 두 큐의 합을 같게 만들 수 없으므로 -1을 리턴한다.

최대 연산 횟수는 queue1의 모든 값을 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1로 옮기는 경우이므로 n + 2 * n = 3 * n이 된다.

 

728x90
반응형