[프로그래머스/C++] 두 큐 합 같게 만들기 (queue - L2)

 

📌 문제

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

프로그래머스

 

문제를 접근하고 어떤 자료구조를 사용하는지는 너무 명확해서 구현까지는 금방 했다.

자료구조도 한 원소의 값의 범위가 크기 때문에 long long 으로 선언하는 것만 조심하면 된다.

하지만 문제는...

도대체 첫번째 테스트1가 왜 통과되지 않는것일까.... 계속 고민을 해보았다...

구글링 해보고 다른 분들 코드를 리뷰해 본 결과 이유는 반복문이 작업을 계속하는 기준을 

큐의 크기 * 2 이상을 돌면 원래 큐로 돌아왔다고 판단했다.

 

하지만 큐의 크기 * 4 만큼 탐색을 해야함을 깨달았다.

왜냐햐면 큐가 핑퐁처럼 주고 받고를 계속 하게 된다면 큐가 원래 상태로 돌아오기 위해서는 큐의 크기 * 2 * 2 만큼 반복해야한다는 점이다...!

 

아직도 코딩테스트는 모르겠고 나는 공부를 많이 해야겠구나 느꼈다...!

 

💻 정답 코드

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

using namespace std;

int solution(vector<int> q1, vector<int> q2) {
    
    //흠.... 엣지 케이스에서 문제가 되고 있는데,,, 뭐지?
    //뭘까~~요
    
    long long sum1 = 0, sum2 = 0;
    int size = q1.size();
    queue<int> queue1, queue2;
    
    for(int i = 0; i < size; i++){      //합을 구합니다.
        sum1 += q1[i]; sum2 += q2[i];
        
        queue1.push(q1[i]); queue2.push(q2[i]);
    }
    
    int answer = 0;
    if((sum1 + sum2) % 2 == 1 ) return -1;
    if((sum1 != sum2) && (size == 1)) return -1;
    
    while(!(sum1 == sum2)){
        
        answer++; 
        if(answer >= size * 4 ){
            answer = -1;
            break;
        }
        
        if(sum1 < sum2){
            
            int temp = queue2.front(); //queue2에서 맨 앞 값 pop 하기
            queue2.pop(); 
            sum2 -= temp;
            
            queue1.push(temp);          //queue1에 해당 값 추가하기
            sum1 += temp;
        }
        
        else{
            int temp = queue1.front(); 
            queue1.pop(); 
            sum1 -= temp;
            
            queue2.push(temp); 
            sum2 += temp;
        }
    }

    return answer;
}