작성일 : 2024.12.02

프로세스 실행 순서 문제

문제 설명

운영체제의 프로세스 관리를 시뮬레이션하는 문제입니다. 다음 규칙에 따라 프로세스가 실행됩니다:

1. 대기 큐에서 프로세스를 하나 꺼냄
2. 더 높은 우선순위 프로세스가 있으면 다시 큐에 삽입
3. 없다면 해당 프로세스 실행 후 종료

예시

프로세스: [A, B, C, D]
우선순위: [2, 1, 3, 2]
실행순서: C → D → A → B

제한 조건

1. priorities 배열

   • 길이: 1 ≤ 길이 ≤ 100
   • 원소: 1 ≤ 원소 ≤ 9
   • 숫자가 클수록 높은 우선순위

2. location

   • 범위: 0 ≤ location ≤ (프로세스 수 - 1)
   • 찾고자 하는 프로세스의 초기 위치

해결 코드

function solution(priorities, location) {
  let answer = 0;
  let arr = [];
  let max_value = Math.max(...priorities);

  for (let i = 0; i < priorities.length; i++) {
    arr.push(i);
  }

  while (priorities.length != 0) {
    max_value = Math.max(...priorities);
    if (priorities[0] < max_value) {
      priorities.push(priorities.shift());
      arr.push(arr.shift());
    } else {
      answer += 1;
      priorities.shift();
      if (arr.shift() == location) {
        return answer;
      }
    }
  }
  return answer;
}

알고리즘 설명

1. 초기화

   • 인덱스 배열 생성 (프로세스 추적용)
   • 최댓값 계산 (최고 우선순위 확인)

2. 프로세스 실행 로직

   while(priorities.length != 0) {
       // 현재 최고 우선순위 갱신
       max_value = Math.max(...priorities);
   
       if(현재 프로세스 우선순위 < 최고 우선순위) {
           // 뒤로 이동
           큐의_끝으로_이동();
       } else {
           // 프로세스 실행
           프로세스_실행();
           목표_프로세스인지_확인();
       }
   }
   

주요 메서드 설명

1. Math.max()

   // 스프레드 연산자로 배열의 최댓값 찾기
   Math.max(...priorities);
   

2. Array 메서드

   // shift(): 배열의 첫 요소 제거 및 반환
   priorities.shift();
   
   // push(): 배열의 끝에 요소 추가
   priorities.push(element);
   

시간 복잡도

• O(n²): 각 프로세스마다 최댓값을 찾아야 함
• n은 프로세스의 개수

공간 복잡도

• O(n): 인덱스 배열 저장
• n은 프로세스의 개수

최적화 포인트

1. 최댓값 캐싱

   • 프로세스가 실행될 때만 최댓값 갱신
   • 불필요한 최댓값 계산 방지

2. 큐 구현 최적화

   • shift/push 대신 포인터 사용 가능
   • 배열 조작의 오버헤드 감소