프로그래머스 두 큐 합 같게 만들기

두 큐 합 같게 만들기←클릭

로직을 구현는 시간보다 어느 부분에서 최적화를 해야하는지 고민이 필요한 문제다.

기본적으로 greedy를 사용하여 구현을 했다.

변수 설정

q1 q2:queue1과 queue2를 queue에 담은 이름
left_hap right_hap:q1과 q2의 배열 내 원소의 합
size: q1의 크기(=q2의 크기)

기본 개념

• vector에 있는 queue1과 queue2의 원소들을 queue에 담는다. (vector로 queue의 pop()을 구현하면 뒤의 값들을 모두 한 칸씩 옮겨야 하므로 시간 복잡도가 $O(n)$이기 때문)
• q1의 합과 q2의 합을 계산하여 left_hap 과 right_hap에 담는다. (left_hap과 right_hap의 합이 홀수이면 -1을 리턴한다.)
• left_hap이 더 크면 q2에서 맨 위의 값을 빼 q1에 넣는다. (언젠가는 q1의 맨 앞 원소가 q2로 가야하기 때문)
• 옮긴 값을 사용하여 left_hap과 right_hap을 계산한다. 이 때 전체 큐의 값을 사용하여 전체 합을 계산하면 시간 복잡도가 $O(n)$이므로 이처럼 계산한다.
• 예시 3과 같이 무한 루프를 돌 수도 있기에 만약 전체 이동 횟수가 4 * size 가 되면 -1을 리턴한다.

코드

github

#define ll long long
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    ll left_hap = 0;
    ll right_hap = 0;
    queue<int> q1;
    queue<int> q2;
    for(int i = 0;i < queue1.size();i++){
        q1.push(queue1[i]);
        left_hap += queue1[i];
    }
    for(int i = 0;i < queue2.size();i++){
        q2.push(queue2[i]);
        right_hap += queue2[i];
    }
    // cout << left_hap << " " << right_hap << endl;
    int size = queue1.size();
    int left_cnt = 0, right_cnt = 0;
    if((left_hap + right_hap)%2!=0) return -1;
    while(left_hap!=right_hap){
        if(answer > size * 4) {
            answer = -1;
            break;
        }
        if(left_hap > right_hap){
            
            left_cnt++;
            q2.push(q1.front());
            left_hap -= q1.front();
            right_hap += q1.front();
            q1.pop();
        }
        else{
            right_cnt++;
            q1.push(q2.front());
            left_hap += q2.front();
            right_hap -= q2.front();
            q2.pop();
        }
        answer++;
    }
    //cout << answer << endl;
    
    return answer;
}

느낀점

시간초과가 왜 나나 했는데 vector에서 큐의 pop()을 구현하려고 queue1.erase(queue1.begin()) 코드에서 시간복잡도가 $O(n)$이 되어서 그랬다.. 그리고 무한 루프의 조건을 q1과 q2의 위치가 서로 바뀌기만 하는 2 * size로 했었는데 예외가 있는지 해결이 안됐다. 어떤 예외가 있는지 생각을 해봐야 겠다...