[ 프로그래머스 | 2022 kako tech internship ] 두 큐 합 같게 만들기 시간초과 해결

프로그래머스 2022 kako tech internship 두 큐 합 같게 만들기 풀이 중,

vector로 푸니까 24번에서 자꾸 시간 초과 나는 오류 발견.

결론은 deque로 구현하면 되고, 나름대로의 분석을 해봤다.

 

---

아래와 같이 각 큐의 합을 비교하는 프로세스로 코드를 짜주었다.

 while(sum1!=sum2){
    if(sum1<sum2){
        //queue1 맨 앞에 queue2 첫번째 원소 삽입
    	//queue2의 첫번째 원소 추출
        //sum2에서 queue2 첫번째 원소 빼줌
        //sum1에서 queue2 첫번째 원소 더해줌
    }
    else{
    	//반대 케이스 수행
    }
}

 

여기서 시간 복잡도를 생각해보자.

각 큐의 최대 크기는 300,000이다. 최악의 경우 각 큐를 모두 훑게 된다.

또한 훑음과 동시에  1) queue2의 첫번째 원소를 찾아 2) queue1의 맨 앞에 넣는다. 3) 마지막으로 queue2의 첫번째 원소를 찾아 지운다.

 

이때 queue에서 맨 앞의 요소를 지우는 것을 vector로 구현한다면, O(n)이 걸린다.

600,000 * 300,000  (큐 2개 당 * 요소 접근) = 180,000,000,000 약 1초가 넘게 걸리고... 아마도 이 부분 때문에 시간초과가 나는 것 같다.

생각해보면 맨 앞의 요소를 삭제하면 나머지 원소를 하나씩 다 옮겨 줘야 하기 때문에 당연히 cost가 많을 수밖에 없다.

 

반면 지우는 행위를 deque 자료구조를 통해 한다면 O(1)만큼의 시간이 걸린다.

deque는 push_front()를 기존 블록에서 맨 앞 블록에 하나를 더 추가해서 push하는 식으로 구현하기 때문이다.

(자세한 건 이 글 참고)

 

 

deque라는 자료형과, vector를 더 효율적으로 관리하는 법에 대해 알 수 있던 계기가 된 문제이다!

 

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <deque>
using namespace std;
long long sum1,sum2;
int i,target,flag;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    deque<int> dq1;
    deque<int> dq2;
    for(i=0;i<queue1.size();i++){
        sum1+=queue1[i];
        dq1.push_back(queue1[i]);
    }
    for(i=0;i<queue2.size();i++){
        sum2+=queue2[i];
        dq2.push_back(queue2[i]);
    }
    if((sum1+sum2)%2!=0){
        answer=-1;
        return answer;
    }
    
    while(sum1!=sum2){
        if(answer>299999){
            answer=-1;
            return answer;
        }
        if(sum1<sum2){
            target=dq2.front();
            dq1.push_back(target);
            dq2.pop_front();
            sum2-=target;
            sum1+=target;
        }
        else if(sum1>sum2){
            target=dq1.front();
            dq2.push_back(target);
            dq1.pop_front();
            // 시간 초과 코드 아래 2줄
            // queue1.erase(queue1.begin());
            // queue2.push_back(target);
            sum1-=target;
            sum2+=target;
        }
        answer+=1;
    }
    
    return answer;
}