💡 PS
[Programmers] 두 큐 합 같게 만들기
date
Jul 14, 2023
slug
make-two-queues-have-the-same-sum
author
status
Public
tags
알고리즘
그리디
summary
2022 KAKAO TECH INTERNSHIP 문제 중 두 큐 합 같게 만들기 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Jul 28, 2023 11:33 AM
언어
문제
풀이
그리디 문제다. 풀이는 비교적 간단하다. 두 큐를 비교해서
queue1의 총 합이 적다면 queue2의 top에 있는 원소를 queue1로, 그 반대라면 queue1의 top에 있는 원소를 queue2에 넣어주면 된다. 단순히 이렇게만 하면 시간초과가 나고, 이 문제의 핵심은 아래 그림이다.
위 그림과 같은 상황에서만 두 큐의 합을 같게 만들 수 있다. 편의상 그림에서는 1과 2로 표시했지만, 어떤 임의의 뭉텅이(그룹)으로 보면 된다.
queue1의 앞 그룹이 queue2의 뒷 부분에 와야하고 queue2의 앞 그룹이 queue1의 뒷 부분에 와야한다.이 원리를 이용하면 최대 이동 횟수를 알 수 있다.
queue의 사이즈 * 2 만큼 이동하는게 최대 이동 횟수가 될 것이다. 나는 이를 이용해 answer가 최대 이동 횟수를 넘어간다면 -1 이 바로 리턴되도록 처리했다.코드
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef long long ll; int solution(vector<int> queue1, vector<int> queue2) { int answer = 0; queue<int> q1, q2; ll one = 0, two = 0; for(int i : queue1) { q1.push(i); one += i; } for(int i : queue2) { q2.push(i); two += i; } while(1) { if (one == two) break; if (answer >= 600000) { answer = -1; break; } if (q1.empty() or q2.empty()) { answer = -1; break; } if (one < two) { int tmp = q2.front(); q2.pop(); one += tmp; two -= tmp; q1.push(tmp); answer++; } else if (one > two) { int tmp = q1.front(); q1.pop(); one -= tmp; two += tmp; q2.push(tmp); answer++; } } return answer; }