3) 프로그래머스 Lv2 - 두 큐 합 같게 만들기

코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

시간 초과 해결에 애쓴 문제

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -2;
    int cnt = 0;
    int q1 = 0;
    int q2 = 0;
    int queue_size = queue1.size();
    long sum1 = 0;
    long sum2 = 0;
    
    for(int i = 0; i < queue_size; i++) {
        sum1 += queue1[i];
        sum2 += queue2[i];
    }
    if((sum1 + sum2) % 2 != 0) {
        return -1;
    }
    queue_size <<= 2;
    while(sum1 != sum2 && queue_size-1 != cnt && q1 != queue_size && q2 != queue_size) {
        if(sum1 > sum2) {
            queue2.push_back(queue1[q1]);
            sum1 -= queue1[q1];
            sum2 += queue1[q1];
            q1++;
        }
        else if(sum1 < sum2) {
            queue1.push_back(queue2[q2]);
            sum2 -= queue2[q2];
            sum1 += queue2[q2];
            q2++;
        }
        cnt++;
    }
    if(sum1 != sum2) {
        answer = -1;
    }
    else {
        answer = cnt;
    }
    
    return answer;
}

생각보다 숫자가 엄청 컸다. 그래서 long type이 필요했다.

숫자가 이동하는데 최대 이동 횟수는 초기 큐의 크기에 4배에 해당하는 크기다. (극단적으로 쏠려있는 경우도 있기 때문)

듣기로는 곱하기는 시간을 많이 잡아먹는다고 들었다. 그래서 "<<"연산자를 활용하여 2칸 shift시키면 4배가 되는 것을 사용했다.

 

이 다음이 문제였는데 초반에는 vector로 되어 있는 큐 였기 때문에 erase를 쓰려고 했지만 계속 시간 초과.

이유는 erase함수는 최악 O(n)의 시간복잡도를 가지고 있으므로 생각보다 오래 걸린다. 

따라서 이를 제거. 

 

대체로 queue1과 queue2의 각 배열값을 하나씩 이동 시키는 방법을 선택했다.

왜냐하면 각 큐의 합은 sum1과 sum2에 저장되기 때문이다.

 

결과는 훨신 빨라졌다.

 

좋아~