풀이
김영준
// 큐를 배열로 구현해서 풀었습니다. class Queue { constructor() { this.queue = []; this.front = 0; this.rear = 0; } // 큐 생성 클래스 enqueue(value){ this.queue[this.rear++] = value; } // 큐 삽입 dequeue(){ const value = this.queue[this.front]; delete this.queue[this.front] this.front += 1; return value; } // 큐 삭제 peek() { return this.queue[this.front]; } // 큐의 첫번째 요소 반환 size(){ return this.rear - this.front; } // 큐의 사이즈 } const solution = (priorities, location) => { const queue = new Queue(); // 큐 생성 for(let i = 0; i < priorities.length; i ++){ queue.enqueue([priorities[i], i]); // 큐에 우선순위를 넣어줌 } priorities.sort((a, b) => b - a); // 우선순위를 내림차순으로 정렬 let answer = 0; // 실행 순서를 나타낼 변수 while(true){ const frontValue = queue.peek(); // 큐의 맨 앞 요소를 가져옴 if(frontValue[0] < priorities[answer]){ // 맨 앞 요소의 우선순위와 현재 우선순위를 비교 queue.enqueue(queue.dequeue()); // 작으면 맨 앞 요소를 삭제하고 다시 맨 뒤에 추가 } else{ const deleteValue = queue.dequeue(); // 맨 앞 요소를 삭제 answer += 1; // 실행함을 나타내려고 1 증가 if(deleteValue[1] === location) return answer; // 실행한 요소의 index가 location이랑 같은 경우 실행 순서를 리턴 } } return answer; };
이종현
// 문제풀이 강의를 보기전 shift함수를 사용하지 않아야한다고 하셔서 // 안쓰고 어떻게 풀어야할까 1시간 이상 고민해보고 로직을 생각해봤는데 // 결국 실패하고 shift함수를 사용해서 문제를 해결하였습니다. // 문제풀이 강의를 본 후 Linked List를 이용한 Queue 클래스를 구현하여 // 해결하는것을 보고 Liked List에 대한 이해가 아직 많이 부족하다는것을 알게되어 // 주말에 Linked List에 대해 좀더 깊게 공부해볼 생각입니다! // shift를 제외한 문제 해결 로직은 거의 동일하네요.. ㅎㅎ function solution(priorities, location) { // 중요도와 해당 index를 담아둘 빈 배열을 선언 const arr = []; // 반복문을 돌며 arr배열에 [중요도, index]를 담아준다 for (let i = 0; i < priorities.length; i++) { arr.push([priorities[i], i]); } // 중요도가 담긴 배열을 내림차순으로 정렬해준다. priorities.sort((a, b) => b - a); let idx = 0; while(true) { // 무한 루프를 돌며 중요도와 arr[0][0]의 크기를 비교하고 // 중요도가 더 클 시 맨앞에 위치했던 arr의 원소를 맨뒤로 위치시킨다. if (arr[0][0] < priorities[idx]) { arr.push(arr.shift()); } else { // 아닐 경우 arr를 cur변수에 저장한다. const cur = arr.shift(); // cur변수의[1]과 location를 비교한다. // 동일할 경우 idx에 1을 더해주고 return 한다. if (cur[1] === location) return idx + 1; // 아닐경우 idx에 1을 더해준다. idx++; } } }
박노철
// 큐 만드는 것이 어려워서 우선 배열을 이용해서 풀었습니다. function solution(priorities, location) { //큐처럼 사용할 배열, {인덱스, 우선순위} 형태로 저장 const q=[]; priorities.forEach((i,idx)=>q.push({idx:idx, priority:i})) let count=1; //우선순위로 정렬 후 처리가 되면 pop priorities.sort((a,b)=>a-b) while(q.length){ let first=priorities.pop(); while(first!== q[0].priority){ // 최우선순위와 같지 않다면,q에서 꺼낸 후 다시 넣기 반복 q.push(q.shift()); } // 최우선 순위와 같다면 꺼내주고 , 원하던 location이면 count리턴 하고 , // 원하던 location이 아니라면 count를 올려준다. let a=q.shift() if(a.idx===location)return count; else count++; } } // shift대신 for...of를 사용하는 방법 function solution(priorities, location) { let ar= []; const priorStack=[] // 우선순위 와 인덱스로 묶어서 저장 priorities.forEach((v,i)=>{ ar.push({lo:i, pri:v}); priorStack.push(v); }) //우선순위 정렬 priorStack.sort((a,b)=>a-b); let flag=false; let count=0; while(true){ let newAr=[]; //shift() 대신 for...of 사용 for(let a of ar ){ if(a.pri===priorStack[priorStack.length-1]){ priorStack.pop(); count++; if(a.lo===location){ flag=true; break; } }else{ newAr.push(a); } } if(flag)break;
이민희
// 실행시간 초과 나서, 수정이 필요해요 ㅜㅜ class Queue { constructor(queue) { this.queue = queue; this.front = 0; this.rear = queue.length - 1; } enqueue(value) { this.queue[this.rear++] = value; } dequeue() { const value = this.queue[this.front]; delete this.queue[this.front]; this.front++; return value; } getMax() { return Math.max(this.queue); } getSize() { return this.rear - this.front; } } function solution(priorities, location) { var answer = 0; // 실행한 프로세스 개수 // location의 프로세스가 실행될 때까지 const myQueue = new Queue(priorities); while (myQueue.getSize() > 0) { let currMax = myQueue.getMax(); let currPriority = myQueue.dequeue(); if (location > 0) { // 꺼낸 원소가 location 원소가 아니라면 location--; if (currPriority == currMax) { answer += 1; // 프로세스 실행 } else { myQueue.enqueue(currPriority); } } else if (location == 0) { // 꺼낸 원소가 location 원소라면 if (currPriority == currMax) { answer += 1; break; } else { myQueue.enqueue(currPriority); location = myQueue.getSize() - 1; } } } return answer; }
// 수정했습니다! /* 1. 큐 클래스를 처음부터 constructor를 통해 초기화하지 말고, 하나씩 enqueue하자. 2. 배열로 구현한 큐 클래스의 메소드로 Math.max를 사용하면, 배열의 빈 값까지 Math.max 메소드 함수 내에 들어가게 된다. 따라서 그냥 내림차순 정렬해서 최대값을 알아내자 */ class Queue { constructor() { this.queue = []; this.front = 0; this.rear = 0; } enqueue(value) { this.queue[this.rear++] = value; } dequeue() { const value = this.queue[this.front]; delete this.queue[this.front]; this.front++; return value; } getSize() { return this.rear - this.front; } } function solution(priorities, location) { var answer = 0; // 실행한 프로세스 개수 // location의 프로세스가 실행될 때까지 const myQueue = new Queue(); priorities.forEach((priority) => { myQueue.enqueue(priority); }); priorities.sort((a, b) => b - a); while (myQueue.getSize() > 0) { let currMax = priorities[answer]; let currPriority = myQueue.dequeue(); if (location > 0) { // 꺼낸 원소가 location 원소가 아니라면 location--; if (currPriority == currMax) { answer += 1; // 프로세스 실행 } else { myQueue.enqueue(currPriority); } } else if (location == 0) { // 꺼낸 원소가 location 원소라면 if (currPriority == currMax) { answer += 1; break; } else { myQueue.enqueue(currPriority); location = myQueue.getSize() - 1; } } } return answer; }
박건우
class Node{ constructor(i, p){ this.i = i; this.p = p; } } class Queue{ constructor(){ this.queue = []; this.front = 0; this.rear = 0; } enqueue(node){ this.queue[this.rear++] = node; } dequeue(){ const node = this.queue[this.front]; delete this.queue[this.front]; this.front += 1; return node; } size(){ return this.rear - this.front; } } function solution(priorities, location) { let answer = 0; let cnt = 0; const queue = new Queue(); // 우선순위, 프로세스 번호 두 가지 값을 기억해야 하기 때문에 // 노드를 생성하여 큐에 삽입 priorities.forEach((v, i) => { const node = new Node(i, v); queue.enqueue(node); }) // 우선순위 배열을 내림차 순으로 정렬합니다. priorities.sort((a, b) => b - a); // 반복문 종료 조건을 뭐라고 해야할지 안떠올라서 1을 집어넣었어요 // 어짜피 모든 프로세스는 언젠가 처리 되기 때문에 무한루프가 돌진 않습니다. while(1){ const node = queue.dequeue(); // cnt는 이때까지 처리 완료된 프로세스 개수에요 // priorities 배열은 내림차 순으로 정렬되었기 때문에 // priorities[cnt]는 항상 가장 높은 우선순위를 가르킵니다. if(priorities[cnt] === node.p) { // 만약 꺼낸 노드의 번호가 location과 같다면 정답을 찾은 겁니당. if(node.i === location) return cnt + 1; cnt += 1; } else queue.enqueue(node); } } // 더 좋은 방법이나 궁금한점 있으시면 댓글 달아주시거나 스크럼때 질문주세요! // 시간복잡도는 제 추측으론 O(N^2)인것 같아요
박주연
//큐 만들기 class Queue{ constructor(){ this.queue = []; this.front = 0; this.rear = 0; } enqueue(value){ this.queue[this.rear++] = value; } dequeue(){ const value = this.queue[this.front]; delete this.queue[this.front]; this.front += 1; return value; } } function solution(priorities, location) { const queue = new Queue(); for (let i = 0; i< priorities.length ; i++){ queue.enqueue([priorities[i],i]); } //우선순위 높은 순으로 정렬 priorities.sort((a,b)=>b-a); let ans = 0; while(priorities.length){ for(const val of queue.queue){ if(val[0] < priorities[ans]){ //우선순위 높은 순서의 숫자와 먼저 비교 queue.enqueue(queue.dequeue()); //큐에서 뺀것을 다시 뒤로 넣기 }else{ //건우 // val[0]이 우선순위가 가장 높을때 // dequeue를 안하셨어용! queue.dequeue(); ans++; if(val[1] === location){ return ans; } } } } }
배열로 푸는건 왜 ….실패……. 😱😱😱😱😱😱😱😱😱😱…강사님 풀이랑 거의 똑같은데…..Why……….(해결완료)
건우님 감사합니다 👍👍👍👍