[알고리즘] 2022 KAKAO TECH INTERNSHIP 두 큐 합 같게 만들기 문제C++

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

프로그래머스

문제 출처

 

문제 이해 & 추상화

두 개의 큐

queue1 = [3, 2, 7, 2]       queue2 = [4, 6, 5, 1] 일때 1번의 진행 과정은 두 가지가 존재한다.

queue1 => Q1, queue2 => Q2로 부르겠다. 

Q1

3

2

7

2

 

Q2

4

6

5

1

 

먼저 queue의 자료구조처럼 진행된다 Q1에서 값을 pop()하면 Q2에 push된다.

Q1 - 1번 진행 (Pop)

2

7

2

 

Q2 - 1번 진행 (Push)

4

6

5

1

3

만약 Q2를 먼저 pop()한다면 Q1에 push된다.

Q1 - 1번 진행 (Push)

3

2

7

2

4

 

Q2 - 1번 진행 (Pop)

6

5

1

 

계획 세우기 (풀이법)

그림1. 이진트리로 나타낸 경우의 수

이렇게 2가지의 경우의 수가 진행할때 마다 증가한다고 확인할 수 있다.

위 그림1은 해당 경우의수를 이진트리로 나타낸 것이다.

 

그림으로 경우의 수를 살피니 제자리로 돌아오는 경우까지 트리를 그리면 2^n => 여기서 n은 Q1 = Q2의 Size(), 즉 길이가 된다.

그렇다면 지금 Q1의 Size = 4이니 16번은 최소 돌려야 최소값을 확인할수 있다.

1. 2^n = > 2^4 => 16 
-> 조건. Q1=Q2<=300,000
2^300000승.. 벌써 말이 안된다. 시간 초과눈 분명하다. -> 완전탐색은 제외시킨다.

 

2. 최선의 방법을 뭘까 생각하다 직관적으로 풀었다.

Q1의 합 > Q2의 합, 즉 Q1의 총합이 Q2의 총합보다 크다면 Q1에서 Pop() Else

Q1의 합 < Q2의 합, 즉 Q2의 총합이 Q1의 총합보다 크다면 Q2에서 Pop()하자

생각으로 이게 제일 최선이었다.

 

구현

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

queue<long long> q1;
queue<long long> q2;
long long hap1=0;
long long hap2=0;
long long total=0;
long long ans=0;
int solution(vector<int> queue1, vector<int> queue2) {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    for(int i = 0; i<queue1.size(); i++) {
        q1.push(queue1[i]);
        hap1 += queue1[i];
        q2.push(queue2[i]);
        hap2 += queue2[i];
    }
    
    total = hap1 + hap2;
        
    for(int i=0; i<queue1.size() *3; i++) {
        long long q1_front = q1.front();
        long long q2_front = q2.front();
        if (hap1 == hap2) {
           return i;
        }
        if (hap1 > hap2) {
            q1.pop();
            q2.push(q1_front);
            hap1-=q1_front;
            hap2+=q1_front;
        } else if(hap1 < hap2) {
            q2.pop();
            q1.push(q2_front);
            hap2-=q2_front;
            hap1+=q2_front;
        }
    }
    return -1;
}

문제점

1번 테스트가 틀렸다. 

이유를 모르겠어서 찾아봤더니 queue1.size() * 2 -> queue1.size()*3이었다.

https://tae-hui.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%91%90-%ED%81%90-%ED%95%A9-%EA%B0%99%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Level2-2022-KAKAO-TECH-INTERNSHIP

다른 블로그를 보고 이해를 해보려고 했지만 어떻게 저걸 그려서 생각하지라는 생각이 든다..