문제설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.제한 사항
- 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
- 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
- location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.
My solution
// 💡 문제 분석 💡
// 스택/큐 이용해서 풀기
// 처음것이 나가서 제일 뒤로 들어가기 때문에 -> 앞에서 나가고, 뒤에서 들어감 : 큐
// 데이터 양이 적으니까 큐 배열로 풀기
// in : 각문서의중요도(자연수배열), 요청한문서idx(idx배열) / out : 몇번째인쇄인지(num)
// 중요도는 1~9 : 현재 작업들 중 가장 큰 중요도 vs 현재 작업 중요도
// 처음에 배열을 돌면서 각 중요도에 몇개의 작업이 있는지 알아서 hash table 에 카운트해서 넣기
// 중요도 비교 후 같으면 작업수행, 큰 중요도 count--(중요도 0 되면, 큰 중요도 다음 레벨로)
// 다르면 대기열 맨뒤로 이동
// location은 계속 위치가 바뀐다
function solution(priorities, location) {
let answer = 0;
// 중요도마다 작업물개수를 파악한 hash table 만들기
const table = new Array(10).fill(0);
const idx = [];
priorities.forEach((v) => {
hashTable(v, table, idx);
});
idx.sort(); // 중요도 순서대로 정렬(반대로 정렬된 상태) : 현재 가장 큰 중요도 idx[idx.length-1]
while (priorities.length > 0) { // 모든 작업이 끝날때까지 반복
const work = priorities.shift();
if (work < idx[idx.length-1]) {
priorities.push(work);
} else {
// 작업수행
table[idx[idx.length-1]]--;
answer++;
if (location === 0) return answer;
}
location = (location === 0) ? priorities.length-1 : --location;
if (table[idx[idx.length-1]] === 0) idx.pop(); // 다음중요도로
}
}
function hashTable(v, table, idx) {
if (table[v] === 0) idx.push(v);
table[v]++;
}중요도 배열(idx)이 다음중요도로 이동할때마다, 요소를 빼주는데 shift를 이용하면 배열자체가 재정렬하는 만큼 필요없는 소요시간이들기때문에, 애초에 오름차순으로 정렬해서 pop을 사용해 재정렬할필요 없게 했다.
근데,
마지막에 idx 배열에서 다음 중요도로 이동하는것을 굳이 요소를 pop해서 이동하지 않고,
index 값을 변경해주면 될 것 같다.
idx.sort();
let importIdx = idx.length-1;
while (..) {
...
if (table[idx[importIdx]] === 0) importIdx--;
}이렇게!! 😆
이렇게 하면 importIdx 변수를 다른코드에서도 활용하면 돼서, 조~금 더 직관적일듯하다!!
...
이번에 라이브코딩 면접을 봤었는데, 제한시간 20분이었다.
뭔가 시간이 제한되고, 긴 시간이 아니라는 생각에(문제의 난이도와는 별개로) 빨리풀어야겠다는 생각만으로 집중을 잘 할 수 없었다.
앞으로는 소요시간을 체크해서 제한 시간을 따로 주는것은 아니지만(물론 모의테스트같은 것을 풀땐 제한해야겠지만)
여유롭게 푸는것이 아니라, 스스로에게 시간이란 압박감을 줘야겠다.
문제 소요시간 : 문제해석, 방향찾기(15m) / 코드작성(30m)
Others
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을 이용한 풀이
- map 이용해서, 각 요소에 현재 작업의 정보를 담은 객체(요청문서인지 불린값, 작업중요도)를 담는다.
- splice 를 이용해 현재 작업을 빼주고
👉 이건 shift 로 대체해도 될듯? - some 이용해서 현재 중요도보다 큰 중요도를 가진 요소가 있는지 확인
👉 있으면 : 대기열 맨뒤에 추가
👉 없으면 : 현재것이 젤 큰 중요도 👉 작업수행(count++) 👉 요청한 문서면 그대로 count 값 반환!
...
다른 사람들의 풀이를 보면, 효율성이 확실히 좋은 것들이 많지만
아닐경우에도, 새로운 관점을 알게돼서 좋다.
Reference
