오늘의 알고리즘 👍

📝 1. 프로세스

• 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

  1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
  2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
  3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  • 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
  • 예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

• 현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

▷ 입출력 예

solution([2, 1, 3, 2], 2) // 1
solution([1, 1, 9, 1, 1, 1], 0) // 5

▷ 내 풀이

function solution(priorities, location) {
  let answer = 0;
  let max = Math.max(...priorities)
  // console.log(max)
  let obj = {...priorities}
  const objKeys = Object.keys(obj)
  const key = Number(objKeys.find((key) => obj[key] === max))
  
  // console.log(max, obj, priorities[key], key)
  let order = [];
  let count = [];
  for(let i = 0; i < priorities.length; i++){
    order.push(priorities[(key + i) % priorities.length])
    count.push((key + i) % priorities.length)
    // console.log(order, count)
  }
  for(let i = 0; i < order.length; i++){
    if(count[i] === location) {
      answer = i + 1
    }
  }
  return answer
}

▷ 해결 못함 ❌

• 내 풀이는 최대값이 같은 경우를 생각을 안해줘서 많은 테스트케이스를 실패했다.
• 시간이 조금 더 있었으면 풀 수 있었을 것 같다.

▷ 수업 풀이

function solution(priorities, location) {
  const origin = priorities[location];
  // location의 인덱스를 가진 데이터를 목표로 잡음
  priorities[location] = 'a';
  console.log(priorities, origin);
  
  let answer = 0;
  while( true ) {
    const search = priorities.indexOf('a');
    // 가장 높은 우선순위인지 확인하기 위해서 원래 priorities를 잠깐 담아줌
    priorities[search] = origin;
    const max = Math.max(...priorities);
    priorities[search] = 'a';
    
    if(priorities[0] === 'a'){
      // 대기열의 가장 앞에 있는 프로세스가 내가 실행하고자 하는 문서일 때
      if(max === origin) {
        return ++answer; // === answer + 1;
      }
    }
    
    if(priorities[0] === max){
      // 현재 실행하려는 프로세스가 가장 높은 우선순위를 가지고 있다면
      // === 현재 프로세스를 실행한다.
      priorities.shift();
      answer++
    } else {
      // 현재 실행하려는 프로세스보다 더 높은 우선순위를 가진 프로셋스가 있다면
      // === 현재 프로세스를 뒤로 보낸다.
      priorities.push(priorities[0]);
      priorities.shift()
    }
  }
}

▷ 재귀함수 사용 풀이

function solution(priorities, location) {
    const origin = priorities[ location ];
    priorities[ location ] = "a";
    
    const recursion = ( count ) => {
        const search = priorities.indexOf( "a" );
        priorities[ search ] = origin;
        const max = Math.max( ...priorities );
        priorities[ search ] = "a";
        
        if( priorities[0] === "a" && origin === max ) return ++count;
        
        priorities[0] === max ? count++ : priorities.push( priorities[0] );
        priorities.shift();
        
        return recursion( count );
    }
    return recursion( 0 )
}

▷ Queue 사용 풀이

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;
	}

	peek(){
		return this.queue[this.front];
	}

	size(){
		return this.rear - this.front;
	}
}

function solution(priorities, location) {
    const origin = priorities[ location ];
    const q = new Queue();
    for( let i = 0; i < priorities.length; i++ ) {
        q.enqueue( priorities[i] );
    }
    q.queue[ location ] = 'a';
    
    const recursion = function( count ) {
        let search = 0;
        for( let i = 0; i < q.queue.length; i++ ) {
            if( q.queue[i] === 'a' ) search = i;
        }
        
        q.queue[ search ] = origin;
        let max = 0;
        for( let num of q.queue ) {
            if( max < num ) max = num;
        }
        q.queue[ search ] = 'a';
        
        const front = q.peek();
        if( front === 'a' && origin === max ) return ++count;
        
        front === max ? count++ : q.enqueue( front );
        q.dequeue();
        
        return recursion( count );
    }
    
    return recursion( 0 )
}

출처: 프로그래머스
출처: 코드캠프