[프로그래머스/C++] 알고리즘 - 두 큐 합 같게 만들기

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 두 큐 합 같게 만들기 를 풀어보도록 하겠습니다.

 

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

프로그래머스

[문제 접근]

저는 문제를 읽으면서 이런 식으로 풀면되지 않을까? 라는 그리디 알고리즘으로 접근했습니다.

queue1의 합이  == 총합 / 2 이면 정답

queue1의 합이  > 총합 / 2 이면 queue1에서 pop하고 queue2에 넣기.

queue1의 합이  < 총합 / 2 이면 queue2에서 pop하고 queue1에 넣기.

그리고 이를 계속 반복했습니다. 멈추는 조건이 필요했습니다.

큐가 비어있을 경우 멈추어야 하고 한 가지 조건이 더 있습니다.

저는 이때  한 멈추는 조건을 어렴풋이 고려해야하는 것을 알고 있었는데, 예외 케이스를 떠올리기가 힘들어서 설마 이거로 틀리겠어?하고 넘어갔었습니다. 근데 이 안일한 생각이 몇 시간을 고민하게 했습니다. 프로그래머스는 시간 초과에 무한루프도 포함하는 것도 덤으로 알았습니다. 그 조건은 바로 queue1과 queue2의 길이 중 더 큰 길이의 *2배보다 pop의 개수가 많을 때입니다.

queue1과 queue2를 모두 한 바퀴 지나갔고 다시 처음 상태로 되돌아왔을 때를 고려해야합니다.

 

[풀이 전략]

deque를 이용하여 문제접근의 내용을 코드로 바꾸었습니다.

 

[코드]

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

using namespace std;

typedef long long ll ; 

ll q1_sum ;
ll q2_sum ; 
ll val ; 

deque<ll> q1;
deque<ll> q2 ; 

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    
    for(auto v : queue1) {
        q1_sum += v; 
        q1.push_back(v);
    }
    
    for(auto v : queue2) {
        q2_sum += v; 
        q2.push_back(v);
    }
    
    val = (q1_sum + q2_sum)/2 ; 
    

    while(1) {
        if(q1_sum == val) break;
        if(q1.empty() || q2.empty()) {answer = -1 ; break ; }
        int tot_size = q1.size()+q2.size();
        if(answer > tot_size*2 ) {answer = -1 ; break ; } // tot_size *2배만큼 돌아야 원래순서대로 돌아감.
        else if(q1_sum > val) {
            ll tmp = q1.front();
            q1_sum -= tmp ;
            q2_sum += tmp ; 
            q2.push_back(tmp); q1.pop_front();
            answer++;
        } else {
            ll tmp = q2.front();
            q1_sum += tmp ;
            q2_sum -= tmp ; 
            q1.push_back(tmp); q2.pop_front();
            answer++;
        }
    }
    return answer;
}

 

추가 풀이 방법 - 투 포인터

#include <string>
#include <vector>
#include <numeric>
#include <iostream>
#include <queue> 

using namespace std;

typedef long long ll ; 

ll q1_sum ;
ll q2_sum ; 
ll val ; 


int st; 
int en ;



int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    int q1_size = queue1.size();
    int q2_size = queue2.size();
    int tot_size = q1_size + q2_size;
    st = 0;
    en = q1_size-1;
    
    q1_sum = accumulate(queue1.begin(),queue1.end(),0);
    q2_sum = accumulate(queue2.begin(),queue2.end(),0);

    ll tot_sum = q1_sum + q2_sum ; 
    ll val = tot_sum / 2 ;
    
    queue1.insert(queue1.end(), queue2.begin(),queue2.end());
    
    
    while(1) {
        if(st > en || answer > tot_size*2) {answer = -1 ; break;} // tot_size *2배만큼 돌아야 원래순서대로 돌아감.
        if(q1_sum == val) break;
        else if( q1_sum > val) {
            q1_sum -= queue1[st % tot_size];
            st++; answer++;
        }
            else {
                en++; answer++;
                q1_sum += queue1[en % tot_size];
            }

        
    }
    
    return answer;
}

 

[배울 점]

- 어렴풋이 고려해야한다는 생각이 들면 넘어가지말고 반례 케이스를 계속 고민하기 -> 코드구현보다 알고리즘 모델링이 더 중요