문제 이해
이 문제는 스택/큐 라는 카테고리를 가지고 있긴하지만, 문제를 풀 때는 어떤 부분에서 그러한지 이해하지 못하였고, 실제로 자료구조를 염두에 두고 풀지는 않았다. 하지만 문제를 풀고 나서 보니 실행 대기 큐가 진짜 큐 자료구조를 뜻하는 것이였다는 것을 알게 되었다.
큐(Queue)
선입선출, 먼저 들어온 것이 먼저 나간다.
위 큐의 정의에 맞춰서 해석하면, 실행 대기 큐에는 이미 프로세스가 들어가 있는 상태이고 들어간 순서대로 나오면서 이를 우선순위에 맞게 실행(or 재정렬(?))하시오 라는 의미이다.
아래는 많이 잘못된 풀이였다. 실제로 답도 제대로 나오지 않는다. 그럼에도 기록의 의미로 남겨놓는다. 조건에 맞을 때, 큐에 넣은 방식으로 접근했고, 뒤에서부터 탐색을 하여 맞는 조건에 끼워넣기(use splice)를 구현하였었다.
function solution(priorities, location) {
const queue = [];
for (let i = 0; i < priorities.length; i++) {
const obj = {
priority: priorities[i],
location: i,
};
if (queue.length > 0) {
let j = queue.length - 1;
while (j >= 0) {
if (queue[j].priority <= priorities[i]) {
queue.splice(j, 0, obj);
break;
}
j--;
}
if (queue.length == j) queue.push(obj);
} else {
queue.push(obj);
}
}
const finded = queue.findIndex((item) => item.location === location);
return finded + 1;
}function solution(priorities, location) {
const executeQ = []; // 실행한 프로세스를 담음 큐
const delayQ = []; // 실행을 못하고 대기 상태로 넘어간 프로세스를 담은 큐
for (let i = 0; i < priorities.length; i++) {
const sub = priorities.slice(i + 1);
const sMax = sub.length > 0 ? Math.max(...sub) : 0;
const dMax = delayQ.length === 0 ? 0 : Math.max(...delayQ.map((o) => o.p));
if (priorities[i] > sMax) {
if (priorities[i] >= dMax) {
executeQ.push({
p: priorities[i],
l: i,
});
} else {
const dI = delayQ.findIndex(({ p, l }) => p === dMax);
executeQ.push(delayQ[dI]);
delayQ.push({
p: priorities[i],
l: i,
});
delayQ.splice(dI, 1);
}
} else if (priorities[i] < sMax) {
delayQ.push({
p: priorities[i],
l: i,
});
} else {
executeQ.push({
p: priorities[i],
l: i,
});
}
}
// ✅
delayQ.sort((a, b) => {
if (a.p === b.p) return a.l - b.l;
else return b.p - a.p;
});
const arr = executeQ.concat(delayQ);
return arr.findIndex((item) => item.l === location) + 1;
}문제는 체크박스 코드 부분이다. 내가 이해한바로는 대기로 넘어가 프로세스는 따로 검색 과정이 없이 처음에 들어온 순서대로 실행이 되는 것으로 이해했다. 그런데 이게 항상 그런것은 아니였다. 정확히는, 실행하기 위해서 뽑힌 프로세스가 실행 조건에 부합하지 않으면 다시 큐의 맨 뒤로 들어가게 된다. 그리고 다시 차례가 돌아온 후 실행 조건에 부합되어 실행이 되거나, 자신보다 낮은 우선순위의 프로세스가 나와서 비교 후 실행되거나 하는 순서로 실행되는 것이였다. 이러한 과정에 대한 해석을 문제 속에서 어떻게 알 수 있는지 궁금했다. 큐라는 자료구조를 음미해보면 알 수 있는 부분일까에 대해서도 의문이긴하다. (개인적으로 저런 부분에 대한 것은 문제 내에 명시적으로 표현해줘야하는 것 아닌가 하는 생각이 든다. 간혹 이러한 문제들이 있는 것 같다. 😨)
위 과정을 예시를 통해서 도식화하면 아래와 같다.
-
예시1
INPUT [2, 1, 3, 2], 2 OUTPUT 1
-
예시2
INPUT [1, 1, 9, 1, 1, 1], 0 OUTPUT 5
-
예시3
INPUT [2, 3, 3, 2, 9, 3, 3], 3 OUTPUT 6
위 도식화를 그리면서 느낀 것인데, 굳이 실행큐를 따로 만들지 않고 기존 큐에 잘라내고(splice or shift) 넣고(push)를 통해서 비교하도록 구현하는게 좀 더 나을거 같다는 생각이 들었다.(아래 코드는 따로 실행큐를 만들었다.)
function solution(priorities, location) {
const pQ = priorities.map((p, i) => ({ p, l: i }));
const executeQ = [];
while (executeQ.length < priorities.length) {
const target = pQ[0];
const sub = pQ.slice(1);
const subMax = sub.length > 0 ? Math.max(...sub.map(({ p, l }) => p)) : 0;
if (subMax <= target.p) {
executeQ.push(target);
pQ.splice(0, 1);
} else if (subMax > target.p) {
pQ.splice(0, 1);
pQ.push(target);
}
}
const finded = executeQ.findIndex(({ l }) => l === location);
return finded + 1;
}사실 나의 코드가 그렇게 깔끔하지 못하여 다른 코드들을 찾아보았는데, 대부분 아이디어는 비슷했다. 그 중 내 아이디어와 유사하지만 더 깔끔하고 가독성 좋은 코드를 소개한다.
function solution(priorities, location) {
var list = priorities.map((t, i) => ({
my: i === location,
val: t,
}));
var count = 0;
while (true) {
var cur = list.splice(0, 1)[0];
if (list.some((t) => t.val > cur.val)) {
list.push(cur);
} else {
count++;
if (cur.my) return count;
}
}
}나는 비교하기 위해서 현재 큐의 프로세스 이후의 값을 가져와서 가장 큰값과 비교하였지만, 여기서는 some을 메소드를 이용하였다. 또한 list 에서만 변형이 일어나는데, 나는 pQ와 executeQ 사이에서 프로세스를 주고 받는 관계를 만들어주었다. 사실 위에서도 언급했지만 executeQ 없이 pQ 하나로만도 구현이 가능한 문제였다. 두 큐의 관계때문에 좀 더 복잡해진 부분이 있다.