두 큐 합 같게 만들기
두 큐의 합 같게 만들기
아직 맞추지 못한 문제다. 테스트 케이스는 통과하지만 채점 과정에서 시간 초과나 런타임 에러, 코어 덤프 등이 뜬다. 풀이법을 발견하면 블로그를 수정하여 완성하겠다.
문제를 해결했다. 정답은 블로그 맨 아래에 있다.
2022 KAKAO TECH INTERNSHIP 문제라는데, 다섯 시간 이상 이것만 붙들고 있어도 아직까지 답을 찾지 못했다. 카카오라는 회사는 인턴에게 도대체 얼마나 대단한 능력을 요구하는 것일까?
문제
문제 설명
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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가지 방법이 있습니다.
1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. 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 해주세요.
제한 사항
- 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
- 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
- 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
풀이
공통적으로 sum 함수는 아래 것을 사용한다.
const sum = (a) => a.reduce((a, i) => a + i, 0n);
숫자 뒤에 n은 BigInt 표시로, 문제의 주의사항에도 적혀 있듯 sum값이 꽤 클 수 있기 때문에 주의하라는 경고 때문에 이렇게 만들었다. 아래 solution함수에서도 같은 이유로 숫자들을 BigInt로 변환해 두었다.
이것을 루프문으로 전개할 경우 약간 빨라지긴 하지만 대부분의 시간 초과 실패를 극복하지 못했다. 따라서 단순한 버전으로 유지하였다.
큐에서 원소를 이동하는 작업은 shift로 정의되며, 아래 두 가지 버전을 사용한다.
// 복사된 큐를 반환
function shift(queue1, queue2) {
const q1 = [...queue1];
const q2 = [...queue2];
q2.push(q1.shift());
return [q1, q2];
}
그러나 복사된 큐를 반환하는 버전의 경우 채점 과정에서 메모리 초과로 인해 core dump되거나 runtime error가 발생하면서 실패한다. 어쩔 수 없이 원본에 수정을 가하는 버전을 사용해야 했다.
// Mutate the original
function shift(q1, q2) {
q2.push(q1.shift());
return [q1, q2];
}
이 버전을 사용할 경우 BFS탐색은 불가능하다.
또한 함수 시그니처에 따라 아래 solution함수를 사용한다.
function solution(queue1, queue2) {
queue1 = queue1.map((n) => BigInt(n));
queue2 = queue2.map((n) => BigInt(n));
const target = sum([...queue1, ...queue2]) / 2n;
// const min = finderDFS([queue1, queue2], 0, target);
// const min = finderBFS([queue1, queue2], target);
// const min = finderLoop([queue1, queue2], target);
const min = finderPtr([queue1, queue2], target);
return min === Infinity ? -1 : min;
}
DFS 탐색(재귀)
// DFS version of finder
function finderDFS([q1, q2], n, target) {
if (n >= (q1.length + q2.length) * 2) return Infinity;
const s1 = sum(q1);
const s2 = sum(q2);
if (s1 === target || s2 === target) {
return n;
}
if (s1 === 0 || s2 === 0) return Infinity;
if (s1 > target) return finderDFS(shift(q1, q2), n + 1, target);
else return finderDFS(shift(q2, q1), n + 1, target);
}
현재까지 가장 간결하게 작성된 코드이다. 아래 루프 버전은 이 재귀 버전을 루프로 풀어쓴 것에 불과하다.
if (n >= (q1.length + q2.length) * 2) return Infinity;
큐에 shift연산을 반복하여 최초의 자기 자신으로 돌아오는 주기(frequency)는 전체 큐의 길이 * 2이다. 따라서 이보다 더 깊이 탐색할 필요는 없다.
if (s1 === target || s2 === target) {
return n;
}
목표를 달성했다면 n값을 반환. 위에는 or함수로 표현했지만 사실 s1이 target이면 s2도 target이다. 즉 위의 조건을 and로 해도 의미하는 바는 같다. 단지 조금이라도 계산을 덜 하기 위한 트릭에 불과하다.
if (s1 === 0 || s2 === 0) return Infinity;
이 경우는 한쪽 큐가 비어버린 경우를 처리한다. 즉 DFS탐색이 답을 찾지 못하고 끌나는 조건이다.
if (s1 > target) return finderDFS(shift(q1, q2), n + 1, target);
else return finderDFS(shift(q2, q1), n + 1, target);
큐의 원소의 개수의 합이 이미 target을 초과한 경우, 거기에 원소를 더 밀어넣어봤자 목표에서 멀어질 뿐이다. 따라서 탐색 가지의 한쪽은 항상 무효다. 이 조건이 가능했기 때문에 Mutation 버전 shift를 사용할 수 있었다. 그렇지 않았다면 원래 큐의 상태를 알아야 해서 원소를 복사하여 넘겨주는 shift를 써야 했었다. 그리고 그 shift는 메모리를 쳐묵한다. 매우 많이 쳐묵한다.
DFS 탐색 가지가 한쪽으로만 들어가기 때문에(그게 좌측일지 우측일지는 sum값을 비교해보기 전에는 모른다) 루프 버전으로 바꿀 때 따로 스택을 만들지 않아도 되었다.
어쨌든 이 DFS버전은 시간 초과로 뻗었다. 그래서 BFS버전을 만들어보았다.
BFS 탐색
위의 DFS탐색을 BFS로 바꾸면 혹시 빨라질까 해서 ChatGPT한테 변환을 부탁하였다.
// ChatGPT helped me
// BFS version of finder
// It worse
function finderBFS([q1, q2], target) {
const visited = new Set();
const queue = [{ q: [q1, q2], n: 0 }];
while (queue.length > 0) {
const {
q: [q1, q2],
n,
} = queue.shift();
const s1 = sum(q1);
const s2 = sum(q2);
if (s1 === target || s2 === target) {
return n;
}
if (s1 === 0 || s2 === 0 || visited.has(`${s1},${s2}`)) continue;
visited.add(`${s1},${s2}`);
queue.push({ q: shift(q1, q2), n: n + 1 });
queue.push({ q: shift(q2, q1), n: n + 1 });
}
return Infinity;
}
ChatGPT가 초안을 쓰고 내가 다듬었다. 다듬은 부분은 5%가 채 되지 않는다. finderDFS버전을 채팅창에 그대로 복사한 뒤에 “이걸 BFS버전으로 만들어 줘” 하니까 진짜로 만들어 주었다.
그러나 BFS버전이 DFS보다 더 느렸다. 따라서 이것은 폐기되었다.
DFS 탐색(루프)
// Loop version of finder
function finderLoop([q1, q2], target) {
let n = 0;
let limit = (q1.length + q2.length) * 2;
while (limit-- > 0) {
const s1 = sum(q1);
const s2 = sum(q2);
if (s1 === target || s2 === target) {
return n;
}
if (s1 < target) {
[q1, q2] = [q2, q1];
}
shift(q1, q2);
n++;
}
return Infinity;
}
탐색 가지가 한쪽으로만 뻗어가기 때문에 스택 없이 구현한 DFS이다. 하지만 원래 DFS버전보다 유의미하게 빠르질 않다. 아니 확실히 빠르긴 빠른데 테스트를 통과 못하는 건 매한가지다.
포인터 기반 탐색(DFS?)
// Pointer calculation
function rangeSum(q, a, b) {
let len = q.length;
a = a % len;
b = b % len;
let i = a;
let acc = 0n;
while (i !== b) {
acc += q[i];
i = (i + 1) % len;
}
return acc;
}
function finderPtr([q1, q2], target) {
const q = [...q1, ...q2];
const len = q.length;
let sep1 = len / 2;
let sep2 = len;
let n = 0;
while (n < len * 2) {
const s1 = rangeSum(q, sep2, sep1);
const s2 = rangeSum(q, sep1, sep2);
if (s1 === target || s2 === target) {
return n;
}
if (s1 === 0 || s2 === 0) return Infinity;
if (s1 < target) {
sep1 = (sep1 + 1) % len;
} else {
sep2 = (sep2 + 1) % len;
}
n++;
}
return Infinity;
}
포인터 기반 탐색의 경우, 두 큐를 하나로 붙이고 sep1, sep2 포인터를 통해서 큐의 범위를 지정한다. 어차피 두 큐들이 shift연산을 수행해도 원소는 그 안에서 순환할 뿐이라는 아이디어에서 출발했다. 내가 2023년 5월 1일 현재 만들 수 있는 가장 빠른 버전이다.
그러나 이것도 역시 루프문 기반 DFS탐색 함수와 거의 비슷한 속도를 낸다.
아래는 내가 달성한 최고 상태의 테스트 결과이다.
테스트 1 〉 통과 (0.26ms, 33.6MB)
테스트 2 〉 통과 (0.16ms, 33.5MB)
테스트 3 〉 통과 (0.24ms, 33.5MB)
테스트 4 〉 통과 (0.27ms, 33.5MB)
테스트 5 〉 통과 (0.94ms, 33.7MB)
테스트 6 〉 통과 (2.38ms, 37.3MB)
테스트 7 〉 통과 (2.57ms, 37.4MB)
테스트 8 〉 통과 (2.44ms, 37.5MB)
테스트 9 〉 통과 (8.31ms, 38.1MB)
테스트 10 〉 통과 (36.08ms, 38.3MB)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 통과 (1485.76ms, 62.5MB)
테스트 14 〉 통과 (1365.59ms, 63.1MB)
테스트 15 〉 실패 (시간 초과)
테스트 16 〉 통과 (8396.75ms, 64.8MB)
테스트 17 〉 통과 (1475.18ms, 65.9MB)
테스트 18 〉 실패 (시간 초과)
테스트 19 〉 실패 (시간 초과)
테스트 20 〉 실패 (시간 초과)
테스트 21 〉 실패 (시간 초과)
테스트 22 〉 실패 (시간 초과)
테스트 23 〉 실패 (시간 초과)
테스트 24 〉 실패 (시간 초과)
테스트 25 〉 통과 (3.07ms, 37.7MB)
테스트 26 〉 통과 (1.92ms, 37.3MB)
테스트 27 〉 통과 (1.79ms, 37.3MB)
테스트 28 〉 실패 (시간 초과)
테스트 29 〉 통과 (10.51ms, 40.1MB)
테스트 30 〉 실패 (시간 초과)
테스트 16이 통과되느냐 실패되느냐 정도의 사소한 차이가 있을 뿐 DFS기반 탐색 함수는 모두 위와 비슷한 결과를 보인다.
이상이 오늘 내가 하루종일 붙들고 있었던 “두 큐 합 같게 만들기”의 기록이다. 못 풀면 못 풀었지 답을 보진 않을 생각이다. 혹시 어쩌면 자바스크립트라는 언어의 한계로 영영 풀 수 없는 문제일지도 모른다. 그렇다면 C언어로 위 루프문 기반 해법을 작성하면 다 풀릴지도 모른다는 건데, 여기서 더 빨리 할 수 있는 해법이 정 없다면 시도해 볼 생각이다.
풀이(진짜)
const sum = (a) => a.reduce((a, i) => a + i, 0n);
function finderPtr(q, target) {
const len = q.length;
let sep1 = len / 2;
let sep2 = 0;
let n = 0;
let s = sum(q.slice(sep2, sep1));
while (n < len * 2) {
if (s === target) {
return n;
}
if (s < target) {
s += q[sep1];
sep1 = (sep1 + 1) % len;
} else {
s -= q[sep2];
sep2 = (sep2 + 1) % len;
}
n++;
}
return Infinity;
}
function solution(queue1, queue2) {
const q = [...queue1, ...queue2].map((n) => BigInt(n));
const target = sum(q) / 2n;
const min = finderPtr(q, target);
return min === Infinity ? -1 : min;
}
큐에서 원소를 빼거나 더했다고 해서 큐 전체의 합계를 재계산할 필요가 없다는 아이디어가 생각났다. shift연산을 할 때 이동하는 원소만큼 한쪽의 큐에서 더해주고 다른 한 쪽의 큐에서 빼 주면 그게 해당 큐의 합계다.
그리고 위의 아이디어들에서 파생된 바대로, 한쪽의 합계가 target을 충족하면 다른 한쪽은 계산할 필요가 없으므로 처음에 queue1의 합계를 구해놨으면 해당 큐의 원소들이 target에 도달하는지만 보면 된다.
이 코드는 모든 테스트를 통과했다. 못 풀 줄 알았는데 어째 블로그 올리고 나서 산책 한 번 나갔다 오니까 문제가 풀려버렸다. 그렇다 이 글을 쓰는 날짜도 5월 1일이다.
댓글남기기