[프로그래머스] 두 큐 합 같게 만들기 C++
in Study on Coding Test
잦은 함수 사용으로 삽질하던 기억이 남아서 작성하는 포스트
정답제출코드
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
// 큐 형태의 큐 원소 합
long long que_sum(queue<int> queue)
{
long long return_sum = 0;
for (int i = 0; i < queue.size(); ++i)
{
return_sum += queue.front();
// 더하고 난 뒤에 맨 뒤로 보내기.
queue.push(queue.front());
queue.pop();
}
return return_sum;
}
int solution(vector<int> queue1, vector<int> queue2) {
long long queue1_sum = 0, queue2_sum = 0;
// 큐 선언 및 큐 형성
queue<int> q1, q2;
// 길이가 같은 두개의 큐의 길이 미리 저장.
int queue_size = queue1.size();
for (int i = 0; i < queue_size; ++i)
{
q1.push(queue1[i]);
q2.push(queue2[i]);
}
queue1_sum = que_sum(q1);
queue2_sum = que_sum(q2);
long long queue_sum = (queue1_sum + queue2_sum);
// 홀수라면 두 큐의 합이 같아지지 않음.
// -1을 리턴한다.
if (queue_sum % 2 == 1)
return -1;
queue_sum /= 2;
// 두 큐를 순회하며 목표 값보다 큰 값이 있는지 확인한다.
// 큰 값이 있다면 절대 만들 수 없으므로 -1을 반환해야한다.
for (int i = 0; i < queue_size; ++i)
{
int q1_cur = q1.front();
int q2_cur = q2.front();
if (q1_cur > queue_sum || q2_cur > queue_sum)
return -1;
else
{
q1.push(q1_cur);
q1.pop();
q2.push(q2_cur);
q2.pop();
}
}
// 논리 : 합이 더 큰 쪽의 큐에 있는 원소를 옮긴다.
int count = 0;
while(true)
{
if (queue2_sum > queue1_sum)
{
int q2_front = q2.front();
queue2_sum -= q2_front;
queue1_sum += q2_front;
q1.push(q2_front);
q2.pop();
count++;
}
else if (queue1_sum > queue2_sum)
{
int q1_front = q1.front();
queue1_sum -= q1_front;
queue2_sum += q1_front;
q2.push(q1_front);
q1.pop();
count++;
}
else if (queue1_sum == queue2_sum)
{
return count;
}
// 큐를 여러번 순환시켰는데 방법이 안나오는 경우 -1 리턴
// 4 곱하기인 이유는 전체 배열의 길이는 2 * queue_size이고
// 전부 한번씩 회전시키면 4 * queue_size가 되므로.
if (count > 4 * queue_size)
return -1;
}
}
소스코드 설명
큐 두개를 새로 만들어서 벡터의 원소를 각각 새로 만든 두 큐에 넣음.
두 합이 홀수인 경우 그냥 -1을 반환한다.
두 합을 2로 나눈 수 보다 큰 수가 큐 안에 있을 경우 절대 조건이 성립할 수 없으므로 이 역시 -1을 반환한다.
두 큐 중에서 합이 더 큰 큐에 있는 원소를 다른 큐로 옮긴다. 이를 반복한다.
삽질한 내용
아래는 내가 삽질했던 코드이다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
long long q_sum(vector<int> queue)
{
long long return_sum = 0;
for (int i = 0; i < queue.size(); ++i)
{
return_sum += queue[i];
}
return return_sum;
}
int solution(vector<int> queue1, vector<int> queue2) {
long long queue1_sum = 0, queue2_sum = 0;
// 길이가 같은 두개의 큐의 길이 미리 저장.
int queue_size = queue1.size();
queue1_sum = q_sum(queue1);
queue2_sum = q_sum(queue2);
long long queue_sum = queue1_sum + queue2_sum;
// 같은 수의 합 저장
queue_sum /= 2;
// 두 큐를 순회하며 목표 값보다 큰 값이 있는지 확인한다.
// 큰 값이 있다면 절대 만들 수 없으므로 -1을 반환해야한다.
for (int i = 0; i < queue_size; ++i)
{
if (queue1[i] > queue_sum || queue2[i] > queue_sum)
return -1;
}
// 논리 : 합이 더 큰 쪽의 큐에 있는 원소를 옮긴다.
int count = 0;
while(true)
{
queue2_sum = q_sum(queue2);
queue1_sum = q_sum(queue1);
if (queue2_sum > queue1_sum)
{
queue1.push_back(queue2[0]);
queue2.erase(queue2.begin());
count++;
}
else if (queue1_sum > queue2_sum)
{
queue2.push_back(queue1[0]);
queue1.erase(queue1.begin());
count++;
}
else if (queue1_sum == queue2_sum)
{
// 목표값을 달성했을 경우
if (queue1_sum == queue_sum)
return count;
}
// 큐를 여러번 순환시켰는데 방법이 안나오는 경우 -1 리턴
// 4 곱하기인 이유는 최대 횟수를 넉넉하게 잡으려고.
if (count > 4 * queue_size)
return -1;
}
}
요약을 하자면 처음엔 큐를 사용하지 않고 벡터만을 사용하였고, 무한 반복문을 돌 때 함수 사용을 너무 자주했다.
함수를 호출할 때 마다 시간이 걸린다는 것을 간과하여 큐1과 큐2에 있는 원소들의 합을 구할 때 마다 함수호출을 하여 시간을 지연시켰다.
그 결과 정답률이 63.6%에 그쳤다.
이 분의 글을 참조하여 합을 구하는 함수는 맨 처음에 한번만 사용하도록 하고,
함수를 이용해서가 아니라 큐의 원소를 옮길 때 변수를 조작하는 방식으로 반복문을 돌 때 마다 새로운 원소의 합을 구하도록 코드를 바꾸었고 그 결과 정답률 100%을 달성할 수 있었다.
반복문을 돌 때 함수 사용을 최대한 지양하도록 해야겠다.
