프로그래머스-프로세스

목차

1.문제

2.문제 풀이과정

3.타인의 코드 분석

 

1.문제

 

 

2.문제 풀이과정

2-1.문제의 요구사항

• 우선순위와 위치라는 두 가지 조건을 동시에 만족시키는 프로세스를 찾아내는 것입니다. 
• 대기 큐의 맨 앞에 있는 프로세스보다 더 높은 우선순위를 가진 프로세스가 큐 안에 존재한다면, 맨 앞의 프로세스는 실행되지 않고 다시 큐의 맨 뒤로 이동한다.
• 우선순위가 가장 높은 프로세스만 순차적으로 실행되며, 이때마다 실행 횟수를 카운트한다. 
• 대기 큐 초기 상태에서 내가 알고 싶었던 특정 위치(location)에 있던 프로세스가, 위 규칙에 따라 몇 번째로 실행되는지 그 순서를 반환해야 한다.

2-2.문제의 접근과정

 

이 문제의 경우에는 큐를 어떻게 효과적으로 조작할 것인가?가 핵심입니다. 단순히 순서대로 꺼내는것이 아니라 상황에 따라 다시 뒤로 넣어야 하기 때문에 큐의 특징을 그대로 활용해야 된다고 생각했습니다.

• 데이터 구조화: 각 프로세스는 단순히 우선순위 값만 가지는 게 아니야. 처음에 주어진 위치를 기억해야 하므로, (인덱스, 우선순위) 형태의 객체(혹은 배열)로 묶어서 큐에 넣습니다.
• 우선순위 비교: 큐에서 맨 앞에 있는 프로세스를 꺼낸 후, 나머지 큐에 있는 모든 프로세스들의 우선순위와 비교를 합니다.
  • 더 높은 우선순위가 있다면? 방금 꺼낸 프로세스를 큐의 맨 뒤로 다시 보낸다.
  • 더 높은 우선순위가 없다면? 해당 프로세스를 실행(Pop)하고, 실행 횟수를 카운트한다.
• 목표 추적: 실행한 프로세스의 인덱스가 초기 location과 일치하는지 매번 확인을 하고. 일치한다면 그때의 카운트 값이 바로 우리가 찾는 정답입니다.

2-3.문제를 풀때의 의사코드

 

1. 초기화

• 큐(Queue)에 (초기 인덱스, 우선순위) 쌍을 순서대로 반복문을 돌리면서 삽입한다.
• 실행 횟수를 기록할 변수 `answer = 0`을 선언한다.

2. 큐가 빌 때까지 다음 과정을 반복한다 (while(!queue.isEmpty())~~)

• 큐에서 맨 앞의 요소(current)를 꺼낸다. (초기 인덱스, 우선순위)
• 큐를 반복문을 돌리면서, current보다 우선순위가 높은 요소가 있는지 확인한다. -> 이때 우선순위가 높으면 break를 건다.
• 조건문을 걸고 더 높은 우선순위가 있는 경우에는 꺼냈던 current를 다시 큐의 맨 뒤로 넣는다.
• 그렇지 않고 현재가 가장 높은 경우에는 answer 를 증가(answer++) 
• 만약 꺼낸 current의 초기 인덱스가 찾는 `location`과 같다면 answer를 반환하고 종료한다.

3. 모든 과정을 마친 후 `answer` 값을 리턴한다.

 

아래는 제가 작성한 코드입니다.

3.타인의 코드 분석

코드를 제출을 하고 다른 사람들이 제출을 한 코드를 비교를 해봤는데 유형은 아래와 같았습니다.

• 큐를 사용한 방법
• 우선순위 큐를 사용한 방법
• 리스트를 사용한 방법

3-1.큐를 사용한 방법

 

 

핵심 아이디어: 매번 큐 전체를 검사하는 대신, 정렬된 우선순위 배열을 '정답지'로 미리 만들어두는 방식입니다. 

• 정렬의 이유: 우선순위 배열을 오름차순으로 정렬하면, 배열의 뒤에서부터 값을 확인했을 때 그 값이 바로 "현재 실행되어야 할 가장 높은 우선순위"가 됩니다.
• 비교 방식: 큐에서 프로세스를 하나 꺼낼 때마다, 정렬된 배열의 현재 최댓값과 비교합니다.
  • 값이 같다면: 현재 프로세스가 가장 높은 우선순위이므로, 프로세스를 실행하고(카운트 증가), 다음으로 높은 우선순위를 찾기 위해 배열의 인덱스를 이동시킵니다.
  • 값이 다르다면: 우선순위가 더 높은 프로세스가 뒤에 있다는 뜻이므로, 꺼냈던 프로세스를 다시 큐의 뒤로 보냅니다.

 

3-2.우선순위 큐를 사용한 방법

 

 

우선순위 큐는 자료구조 자체가 우선순위가 높은 데이터를 항상 맨 앞으로 가져오도록 설계되어 있습니다.

• 핵심 아이디어: PriorityQueue의 정렬 기준을 역순(Collections.reverseOrder())으로 설정하면, 항상 가장 큰 우선순위 값이 큐의 맨 위에 위치하게 된다는 점입니다.
• 장점: 큐에서 우선순위가 가장 높은 값을 찾는 과정(peek())이 매우 빠르고 코드가 간결해 보인다는 점입니다.
• 분석: 우선순위가 높은 순서대로 데이터를 뽑아내야 하는 문제의 성격과 가장 잘 맞아떨어지는 자료구조입니다. 다만, 원래의 위치(location) 정보와 우선순위를 매칭해서 관리해야 하므로, 클래스를 따로 정의하거나 데이터를 잘 다뤄야 한다는 점입니다.

3-3.리스트를 사용한 방법

 

 

마지막은 ArrayList를 사용해서 큐처럼 구현하는 방식입니다.

• 핵심 아이디어: List를 큐처럼 사용하여 get(0)으로 맨 앞 요소를 확인하고, 필요 시 remove(0) 후 add()로 맨 뒤로 보냅니다.
• 장점: 인덱스를 활용해 큐의 요소를 직접 다루기 편해, 데이터 양이 적을 때는 가독성이 좋습니다.
• 분석: 앞의 두 방식에 비해 remove(0) 연산 시 리스트 내부의 요소들을 한 칸씩 앞으로 당겨야 해서 성능 면에서는 가장 불리합니다. 

문제 출저

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스