https://school.programmers.co.kr/learn/courses/30/lessons/42587
문제설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- priorities의 길이는 1 이상 100 이하입니다.
- priorities의 원소는 1 이상 9 이하의 정수입니다.
- priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
- location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
- priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.
function solution(priorities, location) {
var index = [];
var cnt = 0;
var max_num = Math.max(...priorities);
var temp_stack = [];
var temp_index = [];
for(var i = 0; i < priorities.length; i++){
index.push(i);
}
while(priorities.length > 0){
var pop_num = priorities.shift();
var num_index = index.shift();
if(max_num > pop_num){
temp_stack.unshift(pop_num);
temp_index.unshift(num_index);
continue;
}
else{
cnt++;
if(location === num_index)
return cnt
while(temp_stack.length > 0){
priorities.push(temp_stack.pop());
index.push(temp_index.pop());
}
if(pop_num == max_num)
max_num = Math.max(...priorities);
}
}
}풀이
문제의 주요한 제약사항은
우선순위가 높은 작업이 있으면 그 작업 먼저 실시하고 실행 되지 못한 작업들은 뒤로 밀리게 된다
라는 내용이었고 문제에서 queue 자료구조를 사용하라고 말하는 것 같아서 unshift, shift함수를 이용해서 큐를 만들었다.(사실 메서드들은 시간 복잡도가 n만큼 나오기 때문에 좋은 방법은 아니다.)
가장 큰 우선순위를 가지는 작업은
var max_num = Math.max(...priorities);를 이용해서 배열의 최대값을 구하고 최대값인 우선순위가 처리되었을 때는 다시 Math.max를 이용하여 최대값을 최신화 하게 하였다.
location을 찾는 방법은 초기 배열과 똑같은 크기의 인덱스만 저장하는 배열을 만들어서 우선순위가 밀려날 때마다 인덱스도 같이 밀려나게 구현을 했다.
후순위로 밀려진 작업들은 temp_stack, temp_index라는 별도의 값과 인덱스를 저장하는 배열을 만들어, 우선순위가 처리되고 난 후에 원래 배열(priorities, index)에 push하여 임시 배열을 비우게 구현을 했다.
느낀점
큐를 링크드리스트 형식으로 구현을 했다면 시간 복잡도를 좀 더 줄일 수 있겠다는 생각과 js로 풀다보니 아직 메서드들에 익숙하지 않다는 생각이 들었다💦.
하반기에 취업활동 끝을 목표로 화이팅하자🔥
