[programmers] 118667번 - 두 큐 합 같게 만들기 (brute force, 2022 KAKAO TECH INTERNSHIP)

1. 문제 및 예제

 

 Brute force 문제임을 알았지만, 어느 정도 돌려야할지 모르겠어서 초반에 시간 초과가 좀 나온 문제다. 그것만 정하면 알고리즘을 세우는데는 문제가 없었다.

---

프로그래머스

---

2. 풀이과정

 

문제를 나누는건 간단하다.

 

1. 가장 큰 값이 전체 합의 반 보다 크거나, 전체 합이 홀수면 -1을 반환.

2. 만약 두 큐의 합이 같다면 count를 정답으로 반환.

3. 큰쪽의 원소를 pop하여 작은쪽에 push

4. 위의 과정 300000만큼 반복(전체 원소를 이동시키는 수)

 

다음은 전체 코드이다.

 

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

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = -1;
    int count = 0;
    
    long long sum1 = 0;
    long long sum2 = 0;
    long long sum = 0;
    
    long long init1 = 0;
    long long init2 = 0;
    
    queue<int> q1;
    queue<int> q2;
    
    int max = -1;
    
    for(auto it : queue1){
        q1.push(it);
        if(max < it)
            max = it;
        sum1 += it;
        init1 += it;
    }
    
    for(auto it : queue2){
        q2.push(it);
        if(max < it)
            max = it;
        sum2 += it;
        init2 += it;
    }
    
    sum = sum1 + sum2;
    
    if(max > sum / 2 || sum % 2 == 1){
        return answer;
    }
    
    for(int i = 0; i < 300000; i++){
        if(sum1 == sum2){
            answer = count;
            break;
        }
        else if(sum1 > sum2){
            int front = q1.front();
            q1.pop();
            
            q2.push(front);
            
            sum1 -= front;
            sum2 += front;
        
        }else if(sum1 < sum2){
            int front = q2.front();
            q2.pop();
            
            q1.push(front);
            
            sum2 -= front;
            sum1 += front;
        }
        
        count++;
    }
    
    return answer;
}

 

3. 결어

 

 처음에는 두 원소가 정확하게 교환되는 수를 찾으려 했는데, 많이 어려웠다. 역시 컴퓨터의 특성을 이용하여 가장 많이 나올 경우의 수를 반복하는 것이 편했다.