728x90
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/118667
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
int answer = 0;
long long quesum1 = 0, quesum2 = 0;
queue<int> q1; queue<int> q2;
for(int i = 0; i < queue1.size(); i++){
quesum1 += queue1[i];
q1.push(queue1[i]);
}
for(int i = 0; i < queue2.size(); i++){
quesum2 += queue2[i];
q2.push(queue2[i]);
}
if((quesum1 + quesum2) % 2 != 0) return -1;
int n = 3 * quesum1;
while(n--){
if(quesum1 > quesum2){
int x = q1.front();
quesum2 += x;
quesum1 -= x;
q2.push(x);
q1.pop();
} else if(quesum1 < quesum2){
int x = q2.front();
quesum1 += x;
quesum2 -= x;
q1.push(x);
q2.pop();
} else{
return answer;
}
answer++;
}
return -1;
}
vector의 erase로 맨 앞 원소를 제거하는 것은 시간복잡도가 O(n)으로 느리기 때문에 queue로 옮겨서 풀었다.
최적의 해를 찾는 방법은 두 큐의 합이 같아질 때까지 원소의 합이 높은 큐에서 낮은 큐로 원소를 옮기는 것이다.
모든 원소들의 합이 홀수인 경우는 두 큐의 합을 같게 만들 수 없으므로 -1을 리턴한다.
최대 연산 횟수는 queue1의 모든 값을 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1로 옮기는 경우이므로 n + 2 * n = 3 * n이 된다.
728x90
반응형
'Algorithm > Programmers' 카테고리의 다른 글
[Programmers] 캐시 (C++) (0) | 2023.03.15 |
---|---|
[Programmers] 오픈채팅방 (C++) (0) | 2023.03.14 |
[Programmers] 주차 요금 계산 (C++) (0) | 2023.03.07 |
[Programmers] 괄호 변환 (C++) (0) | 2023.03.07 |
[Programmers] 신고 결과 받기 (C++) (0) | 2023.02.22 |