2022 KAKAO TECH INTERNSHIP : 두 큐 합 같게 만들기
👉 (프로그래머스) 기출 문제 확인
My solution
// 💡 문제 분석 💡
// in : 두개의 큐(자연수배열), out : 최소횟수(num), 불가능시(-1)
// 불가능한 경우 : 두 합이 홀수인경우, 두 합을 반으로 나눈 값보다 큰 요소가 배열에 있을 경우
// 각 큐의 현재 합을 비교하며, 큰쪽에서 작은쪽으로 요소 이동
function solution(queue1, queue2) {
let answer = -1;
let max = 0;
let total = 0;
let sum1 = queue1.reduce((sum, v) => {
if (v > max) max = v;
return sum + v;
}, 0);
let sum2 = queue2.reduce((sum, v) => {
if (v > max) max = v;
return sum + v;
}, 0);
if (sum1 === sum2) return 0; // 예외처리
total = sum1 + sum2;
// 불가능 처리
if (max > (total / 2)) {
return answer;
} else {
if (total % 2 === 1) return answer;
}
answer = 0;
while(true) {
if (sum1 > sum2) {
const value = queue1.shift();
queue2.push(value);
sum1 -= value;
sum2 += value;
} else if (sum1 < sum2){
const value = queue2.shift();
queue1.push(value);
sum2 -= value;
sum1 += value;
} else {
return answer;
}
answer++;
}
return answer;
} 💻 문제 소요시간 : 문제해석, 방향찾기(20m) / 코드작성(25m
)
...
사실 문제푸는 방법을 못찾아냈다..
분명 예외사항이 있을 것 같고, 딱 맞물리는 풀이가 아닐거라고 생각은 하는데,
일단 작성하고 실행시켜보려고 코드를 짜기 시작했다.
내가 푼 방법은
1. 각 큐배열의 합을 구해서 토탈합을 구한다.
2. 먼저, 혹시모를, 처음부터 정답이 나왔을 예외처리를 해주고,
3. 토탈합을 통해 불가능 처리를 해준다.
4. 그 뒤엔 다시 anwer 를 0으로 셋팅해준 뒤, while 반복문으로 작업수행해주기
5. 각 루프에서 두 큐의 합을 비교해서 큰쪽에서 작을쪽으로 넘겨주는 방식으로 풀었다.
(맞는지 긴가민가 했는데, 시간초과 말고는 틀린게 없어 이렇게 푸는게 맞나보다 ㅎㅎ)
...
시간초과로 실패하고, 테스트 11부터는 시간이 급격히 크게 나오는것으로봐서
푸는방법은 맞는거같은데, 큐를 배열로 풀어서(push, shift 이용) 데이터 크기가 커지니 시간초과가 나온것같다.. 라고 추측했다.
linked list 큐로 다시 풀어봐야겠다.
Others
KAKAO 제시 방향
2022 테크 여름인턴십 코딩테스트 해설 참고
문제에서 요구하는 것은 queue1과 queue2의 원소 합을 같게 만드는 것입니다. 처음 주어진 queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 다음과 같은 탐욕법을 사용하여 해결할 수 있습니다.L > R이라면, queue1의 원소를 queue2로 넘겨줍니다. L < R이라면, queue2의 원소를 queue1로 넘겨줍니다.위 방법이 왜 유효한지 간단하게 증명하면 다음과 같습니다.
앞에서 설명한 방식과 반대로 L > R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정하겠습니다. 이 경우 L = R을 만들기 위해서는 언젠가 L을 감소시키고 R을 증가시켜야 하고, 결국 queue1의 원소를 queue2로 넘겨주는 동작은 반드시 필요합니다. queue2의 원소를 queue1으로 넘겨준 이후에 queue1의 원소를 queue2로 넘겨주든, 이 순서를 반대로 하든 결과는 동일하기 때문에, L > R인 상황에서 L을 감소시키는 방법은 항상 최적이 될 수 있습니다.
이때, 직접 큐(Queue) 자료구조를 이용하지 않고 단순히 배열을 큐로 사용하면 0번 원소를 지우는 과정에서 시간 초과가 발생할 수도 있습니다.
이 방법 이외에도, 각 큐의 원소를 실제로 이동시키지 않고 한 구간의 시작 위치와 끝 위치를 포인터로 지정하여 이동하는 투 포인터(Two Pointers) 방식의 풀이도 존재합니다.
먼저 queue1을 왼쪽, queue2를 오른쪽에 이어 붙이고 하나의 배열처럼 본다고 생각해 봅시다. 이 경우 각 큐에 pop 또는 insert 연산을 하는 것은 배열의 경계를 이동시키거나 맨 앞의 원소를 맨 뒤에 이동시키는 연산을 하는 것이라고 볼 수 있으므로, 각 큐는 이렇게 정의한 배열에서 연속된 구간의 원소로만 이루어진다고 생각할 수 있습니다. 이 상황에서 queue1의 시작과 끝을 나타내는 두 포인터를 적절히 이동시키는 것입니다.
각 큐의 원소의 합은 (L + R) / 2가 되어야 하므로, queue1의 두 포인터 내에 있는 모든 원소의 합이 (L + R) / 2보다 작을 땐 끝 위치를 가리키는 포인터를 이동시키고 (L + R) / 2보다 클 땐 시작 위치를 가리키는 포인터를 이동시키면 됩니다.
이때, 전체 배열의 길이가 2n이므로, 한 포인터 당 최대 2n번의 이동이 필요합니다. 따라서, 총 4n만큼의 작업을 수행한 뒤에도 두 큐의 합을 같게 만들지 못했다면 그 이후에는 이미 탐색했던 구간을 다시 탐색하는 것이므로 의미가 없습니다. 이 경우에는 -1을 반환합니다.
Reference
