길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고,
추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다.
이때 필요한 작업의 최소 횟수를 구하고자 합니다.
한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다.
이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다.
즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다.
예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며,
이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다.
각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요.
단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
queue1
의 길이 = queue2
의 길이 ≤ 300,000queue1
의 원소, queue2
의 원소 ≤ 10^9해당 문제를 위해서 다음과 같은 고려사항을 설정하였다.
1. queue1의 이동횟수가 기존 queue1의 크기와 같으면서 queue2의 이동횟수가 기존 queue2의 크기와 같으면 두 queue의 원소가 서로 교환되었다고 판단하고 -1을 return
2. 두 queue의 원소의 합이 홀수인 경우 두 queue의 합이 같을 수 없으므로 -1 return
3. queue의 이동횟수의 합이 60만을 넘으면 (최대 queue원소의 크기가 30만이므로) -1 return
이후 어떤 방식으로 queue들의 원소를 이동하면 좋을지 생각해보았다.
먼저 각 queue의 원소의 합을 que1_sum
, que2_sum
라는 변수에 각각 할당해주었다.
이후 que1_sum
와 que2_sum
를 비교하여 더 큰 값을 가지는 queue의 원소를 작은 값을 가지는 queue로 이동시키는 행위를 반복하도록 했다.
위와 같은 예시가 있다고 할 때, queue1
의 전체 합은 6 이며 queue2
의 합은 14가 된다. 따라서 queue1
의 합이 더 작기 때문에 queue2
의 첫번째 원소를 queue1
에 넣어주면 아래와 같은 결과를 갖게 된다.
queue1
에 첫번째 원소를 넣어주었음에도 전체 합계가 queue1
이 더 작기 때문에 queue2
에서 다시 queue1
에 원소를 push 해준다.
그렇게 되면 queue1
의 합이 queue2
의 합보다 커지게 되며, 이경우 queue2
에 queue1
의 원소를 push 해준다.
위의 과정을 두 queue
가 같을때 까지 반복한다.
(위의 경우 queue2
의 마지막에 원소 1
이 들어가지 않았다 -> 오타!)
그렇게 되면 위와 같이 queue
가 성립하게 된다.
옮긴 횟수는 총 7이 됨을 알 수 있다. (빠진 원소 1
포함)
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
int answer = -2;
int que1_cnt = 0, que2_cnt = 0, que1Size = queue1.size(), que2Size = queue2.size();
long long que1_sum = 0, que2_sum = 0;
queue<int> que1, que2;
for (int i = 0; i < que1Size; i++) {
que1_sum += queue1[i];
que1.push(queue1[i]);
}
for (int i = 0; i < que2Size; i++) {
que2_sum += queue2[i];
que2.push(queue2[i]);
}
if ((que1_sum + que2_sum) % 2 == 1) return -1;
while(que1_sum != que2_sum && que1_cnt + que2_cnt < 600000) {
int num;
if (que1_cnt == que1Size && que2_cnt == que2Size) return -1;
if (que1_sum > que2_sum) {
// queue1[0] -> queue2, que2_sum up, que1_sum down
num = que1.front();
que2.push(num);
que2_sum += num;
que1_sum -= num;
// que1_cnt up -> move
que1_cnt += 1;
que1.pop();
}
else {
// queue2[0] -> queue1, que1_sum up, que2_sum down
num = que2.front();
que1.push(num);
que1_sum += num;
que2_sum -= num;
// que2_cnt up -> move
que2_cnt += 1;
que2.pop();
}
}
if (que1_cnt + que2_cnt >= 600000 && que1_sum != que2_sum) answer = -1;
else answer = que1_cnt + que2_cnt;
return answer;
}
1. 시간초과(제한사항에 대한)
→ 최대 30만개의 원소를 가질 수 있기 때문에 중간에 제한을 두지 않으면 시간초과가 발생하는 것을 확인하였다. 제한사항에 대한 부분을 숙지하는 습관을 조금 더 들여야할 것 같다.
2. 시간초과(vector의 erase()함수)
→ 테스트케이스24 번에 대한 경우 계속된 시간초과로 애를 먹었다.
→ vector의 erase() 함수의 시간복잡도가 O(n) 이기 때문에 최대 600000 * 300000 까지 커질 수 있기 때문에 시간초과가 발생한다는 것을 알게 되었다.
→ 따라서 vector의 원소를 queue에 넣어 pop() 을 이용하여 시간초과를 해결하였다. pop()의 경우 시간복잡도가 O(1) 이기 때문에 큰 문제가 없었다.