길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
다음은 두 큐를 나타내는 예시입니다.
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.
queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
문제 풀이
처음에는 단순하게 풀이하려 했다. 문제에서 주어진대로 첫번째 q 에서 두번째 q 에 더해준 뒤 각 큐의 합을 구해서 같은지 확인하고 더 작은 쪽에서 큰 쪽으로 넘기는 방식으로.
하지만 큐 하나당 길이가 300,000을 넘어가고, 각 숫자가 최대 10^9 까지 나올 수 있어서 연산할때 시간초과가 날 것 이라 예상하고 초기에 한번씩만 각 큐의 총 합을 구한뒤 그 합을 기준으로 연산을 처리했다.
vector에서 erase 연산을 처리하면서 각 vector에 있는 n 개의 index들을 모두 수정해주다 보니 시간이 너무 오래걸려서, 각 vector에서 queue의 pop 역할은 따로 인덱스를 만들어서 더해주는 방식으로 바꿔서 풀이했다.
두 리스트 모두 큐이므로 앞에서 부터 빠져나가니까 index 두개를 만들어서 각각 0 으로 설정해준 후, 해당 큐에서 pop을 했다고 하면 index를 +1 해주는 방식으로 접근했다.
sum(queue1) > sum(queue2) 이면 queue1 의 index 를 +1 해주고, queue2에 push(queue1[index1])
각각의 큐에서 값을 넘기는 횟수는 큐의 최대 길이 * 3 을 해줬다. 큐를 통째로 갈아도 길이의 두배 정도 만큼의 반복이 이뤄지기 때문에 넉넉하게 3배정도까지 시도해보고 안되면 -1을 return하게 해줬다.
코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
int answer = -1;
long long tmp1=0, tmp2=0;
for (int i=0; i<queue1.size(); i++) {
tmp1 += queue1[i];
tmp2 += queue2[i];
}
int cnt = 0, lim = queue1.size() * 3;
int idx1=0, idx2=0;
while (cnt < lim) {
if (tmp1 == tmp2) {
return cnt;
}
if (tmp1 > tmp2) {
int tmp = queue1[idx1];
tmp1 -= tmp;
tmp2 += tmp;
queue2.push_back(tmp);
idx1++;
}
else if (tmp2 > tmp1) {
int tmp = queue2[idx2];
tmp2 -= tmp;
tmp1 += tmp;
queue1.push_back(tmp);
idx2++;
}
cnt++;
}
return answer;
}
회고
C++에서 #define long long ll 을 인식 못한다는 사실을 몰라서 처음에 접근이 이상했다.
C++ 에서 long long 과 int type을 더하면 longlong 이 된다. int type 은 long long type보다 작으므로 데이터 손실 방지를 위해 자동적으로 형변환을 해준다.
