[카카오 코딩테스트] 두 큐 합 같게 만들기
그리디 알고리즘 & 투 포인터 문제이다.
처음 생각했던 접근방식(오류)
이 문제를 봤을 때 친절한 예제 설명 덕분에 어떻게 풀어야할지 힌트를 얻을 수 있었다.
각 큐의 원소 합이 같아야하기 때문에, 두개의 큐의 전체 합을 알면 2로 나누면 되므로 각각의 큐가 도달해야하는 합을 알 수 있다.
사소해보이지만 이 개념이 문제 풀이를 위한 핵심 개념이고, 막상 바로 떠오르지 않을 수 있었는데 문제에서 친절하게 알려주었다.
그래서 이 다음 떠오른 생각은 그리디 알고리즘으로, 결국 각각의 두 큐의 합이 같아야 하므로,
q1 < q2 (합)일경우, q2에서 꺼내고 q1에 넣고, q1 > q2 (합)일경우 반대로 하면 될것이라 생각했다.
그러나 예제의 설명에 지나치게 의존했던 탓일까,
첫번째 예제에서 q1 < q2인데도 q1에서 먼저 꺼내는 것을 보고 예외사항이 발생할 수 있다고 생각했다.
조금만 더 생각했더라면 아까 논리적으로 두 큐의 합이 같아야 하므로, 결국 큰 쪽 큐에서 반드시 꺼내야하는 상황이 발생하는데,
그걸 놓치고 단순히 그리디 알고리즘으로 풀 수 없고 완전 탐색(N이 30만인데도 불구하고)을 해야겠다고 생각했다.
이 문제는 투 포인터로도 풀 수 있는데, 이 문제를 풀기 직전에 투 포인터 문제를 풀었는데도 떠오르지 않았던 이유는
아직 투 포인터를 응용하는데 있어서 미숙하기 때문이라고 생각한다.
두개의 큐를 합쳐서 하나의 원형 배열로 생각하면, 큐에서 꺼내고 다시 넣는 작업은 각각의 포인터의 인덱스를 조정하는 것과 같고,
숫자의 합이 큰 큐에서 꺼내고 삽입하는 과정을 거친다. 합이 전체 합의 절반이면 기록하고, 최소한의 횟수만 리턴한다.
따라서 논리적인 흐름은 그리디와 같다.
밑에는 잘못된 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <queue>
using namespace std;
int ret;
int minimum = 987654321;
//어.. 근데 무한루프에 빠지는 것을 어떻게 방지하지?
void recur(queue<int> q1, queue<int> q2, int sum, int cnt){
if(sum == ret){
minimum = min(minimum, cnt);
return;
}
if(q1.empty() || q2.empty()){
return;
}
//q1 원소빼서 q2 넣기
int removed = q1.front(); q1.pop();
q2.push(removed);
recur(q1, q2, sum-removed, cnt+1);
int backToQ1 = q2.front(); q2.pop();
q1.push(removed);
//q2 원소빼서 q1 넣기
int removed2 = q2.front(); q2.pop();
q1.push(removed2);
recur(q1, q2, sum+removed2, cnt+1);
int backToQ2 = q1.front(); q1.pop();
q2.push(removed2);
}
int main(){
queue<int> q1, q2;
q1.push(3); q1.push(2); q1.push(7); q1.push(2);
q2.push(4); q2.push(6); q2.push(5); q2.push(1);
//queue1 = 14
//queue2 = 16
ret = 15;
recur(q1, q2, 14, 0);
cout << minimum;
return 0;
}
|
cs |
나름 예제를 대입해서 한번 백트래킹을 써보려고 했는데, depth가 2만을 훌쩍 넘어갈 수 있으므로 실행해보면 스택오버플로우가 발생한다.
합당한 접근방식(그리디)
아까 설명한 그리디 알고리즘으로 풀어보았다.
여기서 주목할 점은 실패조건인데, q1 기준으로 길이가 n이므로, 값이 이동할 때 최대 2n만큼 이동한다.
그렇다면 다시 q2에서 q1으로 이동하는 길이는 2n이고, 총 4n동안 반복하면 처음과 같아지므로 이때까지 두 큐의 합이 같지 않다면 -1.
그리고 수학적인 센스가 있다면 두 큐의 합이 홀수일 경우 두 큐의 합이 같게 만들 수 없으므로 이때도 -1을 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
long long sumQ1 = 0;
long long sumQ2 = 0;
queue<int> q1, q2;
for(auto q: queue1){
sumQ1 += q;
q1.push(q);
}
for(auto q: queue2){
sumQ2 += q;
q2.push(q);
}
if((sumQ1+sumQ2)%2 !=0){
return -1;
}
int maxIteration = (q1.size()+q2.size())*2;
for(int cnt=0; cnt<maxIteration; cnt++){
if(sumQ1 == sumQ2){
return cnt;
}else if(sumQ1 > sumQ2){
q2.push(q1.front());
sumQ1 -= q1.front();
sumQ2 += q1.front();
q1.pop();
}else {
q1.push(q2.front());
sumQ1 += q2.front();
sumQ2 -= q2.front();
q2.pop();
}
}
return -1;
}
|
cs |