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

문제

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

프로그래머스

 

문제 풀이

두 집합은 큐라는 특성을 가지고, 두 집합의 원소의 합이 서로 같아질 때까지 몇 번 연산해야 하는지 구해야 합니다.
여기서 연산은 pop과 insert 한번입니다.

 

우선 설명을 쉽게 하기 위해서 queue1을 F, queue2를 S, queu1의 원소합을 f, queue2 원소의 합을 s라고 하겠습니다.

 

당연하게도! F와 S의 합이 홀수라면 절대로 두 집합의 합은 같아질 수가 없기 때문에, 미리 걸러주는 작업이 필요합니다.

두 합이 짝수라면 이제 계산을 해야 합니다.

 

세 가지 경우가 있습니다.

F와 S가 합이 같은 경우

우리가 원하는 경우의 수이기 때문에, 그냥 연산 결과를 return 해주면 됩니다.

---

F가 S보다 합이 큰 경우

1. F의 front()에 있는 원소 temp를 기록하고 pop 합니다.
2. temp를 S로 push 합니다.
3. f - =temp, s +=temp

---

S가 F보다 합이 큰 경우

1. S의 front()에 있는 원소 temp를 pop 합니다.
2. temp를 S로 push 합니다.
3. f+=temp, s-=temp

---

이렇게 진행하면 됩니다.

하지만 무한정 진행할 수 도 없고, F와 S의 합이 짝수여도 F와 S가 같아질 수 없는 경우의 수가 있을 겁니다.

그렇다면 우리는 그 upper bound를 결정해줘야 합니다.

제가 생각했던 최악의 경우의 수는 단순하게 queue1과 queue2가 서로 뒤 바뀐 경우라고 생각해서 

경우의 수 제한을 최대길이 *2만큼 연산을 해줬습니다.

그랬더니.. 위와 같이 딱 1번 테케에서 틀렸습니다.

범위가 잘못된 걸 알아서, 다시 생각을 해보니 최악의 경우는 다음과 같을 거라고 예상해 봤습니다.

 

우선 queue1이 원소가 더 많다는 가정 하에,

queue1의 원소가 쭈우욱 빠져서 queue2로 옮겨지고, queue2에서 원소가 쭈우욱 빠져서 queue로 가는 경우는

이제 queue1의 길이 *2보다 큰 값입니다. 

따라서 그 범위의 값을 최대길이 *3으로 설정하니 맞았습니다.. ㅎ

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
long long first=0,second=0;
queue<long long> q1,q2;
int solution(vector<int> queue1, vector<int> queue2) {
    for(int i=0; i<queue1.size();i++){
        q1.push(queue1[i]);
        first+=queue1[i];
    }
    for(int j=0; j<queue2.size();j++){
        q2.push(queue2[j]);
        second+=queue2[j];
    }
    if( (first+second)%2!=0){ //홀 수 일때는 절대 두 합이 같을 수가 없음.
        return -1;
    }
    else{
        long long result=0;
        while(1){ 
            if(first==second){
                return result;
            }
            if(result>=max(queue1.size(),queue2.size())*3){ //종료 조건.
                return -1;
            }
            else if(first>second){
                long long temp = q1.front();
                q1.pop();
                first-=temp;
                second+=temp;
                q2.push(temp);
            }
            else if(second>first){
                long long temp=q2.front();
                q2.pop();
                first+=temp;
                second-=temp;
                q1.push(temp);
            }
            result++;
        }
    }
}

 

느낀 점

• 큐의 특성을 활용해서 푸는 문제지만, 종료 조건을 생각하기 조금 까다로웠다.
• 다른 사람 코드를 보니 iterator를 활용해서 끝까지 검사를 한 경우를 종료조건으로 설정했던데 그분은 진짜 천재인 거 같다.