Younho9 NotesProgrammers 42587. 프린터
Title
Programmers 42587. 프린터
Category
AlgorithmTags
Aliases
Programmers 42587. 프린터Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 스택/큐 | lv.2 | 20분 | ✅ |
설계 방법
문서의
index를 담고 있는 큐와priorities큐를 동시에 관리함.문제에 나와있는 설명 그대로 구현함.
코드
javascript
function solution(priorities, location) {
const waiting = priorities.map((_, idx) => idx);
const finished = [];
while (priorities.length) {
const cur = priorities.shift();
const curIdx = waiting.shift();
if (priorities.some((priority) => priority > cur)) {
priorities.push(cur);
waiting.push(curIdx);
continue;
}
finished.push(curIdx);
}
return finished.findIndex((el) => el === location) + 1;
}
function solution(priorities, location) {
const waiting = priorities.map((_, idx) => idx);
const finished = [];
while (priorities.length) {
const cur = priorities.shift();
const curIdx = waiting.shift();
if (priorities.some((priority) => priority > cur)) {
priorities.push(cur);
waiting.push(curIdx);
continue;
}
finished.push(curIdx);
}
return finished.findIndex((el) => el === location) + 1;
}
시간 복잡도
우선순위 배열을 순회하며 (n) 우선순위 배열 내에 현재 요소보다 우선순위가 더 높은 요소가 있는지 검색 (n) => O(n^2)
추가적으로 큐가 최적화되어 있지 않아서 shift 연산 마다 O(n)
=> O(n^2)
어려웠던 점
문제 설명을 따라서 쉽게 풀 수 있었음.
O(n^2) 연산 없이 현재 요소보다 우선순위가 더 높은 요소를 검색할 수 있는지 모르겠음.