https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=csharp
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
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 … 과 같이 표현합니다.
입출력 예
| priorities | location | return |
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.
풀이
큐에 프로세스들을 넣고 하나씩 빼면서 우선순위가 높은 프로세스를 실행해야 한다.
여기서 실행은 아마 큐에 있는 원소를 Deque하는 것을 뜻하는 것 같다.
만약 현재 프로세스가 뒤에 있는 프로세스들보다 우선순위가 낮으면 현재 프로세스를 다시 큐에 넣는다.
앞에 있던 원소(프로세스)가 뒤로 이동하는 큐는 양방향 큐(=덱)다.
따라서 이 문제는 양방향 큐(=덱)로 푸는 문제다.
코드 - 오답
namespace 덱
{
internal class Programmers_프로세스
{
static int MAX = 1000005;
static int[] deque = new int[2 * MAX + 1];
static int head = 0;
static int tail = 0;
public void Push_Back(int num)
{
deque[tail++] = num;
}
public void Push_Front(int num)
{
deque[--head] = num;
}
public void Pop_Back()
{
tail--;
}
public void Pop_Front()
{
head++;
}
public int Front()
{
return deque[head];
}
public int Back()
{
return deque[tail - 1];
}
public int Size()
{
return tail - head;
}
public bool IsEmpty()
{
if (tail - head == 0)
return true;
return false;
}
public int Max()
{
int max = 0;
for (int i = head; i < tail; i++)
{
if (deque[i] > max)
{
max = deque[i];
}
}
return max;
}
public int solution(int[] priorities, int location)
{
int answer = 0;
// Deque 초기화
for (int i = 0; i < priorities.Length; i++)
{
Push_Back(priorities[i]);
}
while (Size() > 0)
{
if (Front() == Max())
{
answer++;
if (Front() == priorities[location])
{
return answer;
}
}
else
{
Push_Back(Front());
Pop_Front();
}
}
return answer;
}
static void Main(string[] args)
{
Programmers_프로세스 p = new Programmers_프로세스();
int[] priorities = { 2, 1, 3, 2 };
int location = 2;
Console.WriteLine(p.solution(priorities, location));
}
}
}
테스트케이스 1만 통과하고 나머지 테스트케이스는 시간초과와 오답이 나왔다.
코드2 - 정답
namespace 덱
{
internal class Programmers_프로세스_정답
{
public int solution(int[] priorities, int location)
{
Queue<(int index, int priority)> queue = new Queue<(int index, int priority)>();
for(int i = 0; i < priorities.Length; i++)
{
queue.Enqueue((i, priorities[i]));
}
int count = 0;
bool isExistHighPriorityProcess = false;
// 큐에 있는 프로세스가 다 비어질때까지 반복
while(queue.Count > 0)
{
(int index, int priority) p1 = queue.Dequeue();
isExistHighPriorityProcess = false;
foreach((int index, int priority) p2 in queue)
{
// p1 프로세스보다 우선순위가 높은 프로세스가 있다면
if(p1.priority < p2.priority)
{
isExistHighPriorityProcess = true;
break;
}
}
// p1 프로세스보다 우선순위가 높은 프로세스가 있다면
if (isExistHighPriorityProcess)
{
// 큐에 p1 프로세스를 넣기.
queue.Enqueue(p1);
}
// p1 프로세스보다 우선순위가 높은 프로세스가 없다면
else
{
// p1은 실행할 프로세스
// 이미 Dequeue를 하면서 실행처리가 되었다.
count++; // 실행횟수 카운트
// 실행된 프로세스의 인덱스가 location(확인할 프로세스 인덱스)와 같으면
if(p1.index == location)
{
return count; // 실행횟수를 반환
}
}
}
// 마지막으로 실행되는 프로세스인 경우
return count; // 마지막 실행횟수(=큐의 크기)를 반환
}
static void Main(string[] args)
{
Programmers_프로세스_정답 p = new Programmers_프로세스_정답();
}
}
}
풀이 시간이 너무 걸려서 다른 사람 코드를 가져왔다.
이 코드는 System.Collections.Generic에 있는 Queue 자료구조를 사용한 코드다.
우선순위가 높은 프로세스를 찾는데 걸리는 연산은 최대 N번이니 시간복잡도는 O(N)이다.
만약 큐에 프로세스가 엄청 많고 우선순위도 뒤죽박죽이면 시간초과가 걸리지 않을까 싶었는데 이 코드는 통과한다.
cf)
[프로그래머스] 프로세스
https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=csharp 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr using System;using System.C
funfunhanblog.tistory.com
복습 1 풀이 (6/12)
[문제]
운영체제는 컴퓨터 시스템 자원을 효율적으로 관리한다.
다음 규칙에 따라 프로세스를 관리한다. 특정 프로세스가 몇 번째로 실행되는지 알아내자.
<규칙>
- 큐에서 대기 프로세스틀 하나 꺼낸다.
- 큐에 있는 대기 프로세스들 중 우선순위가 더 높은 프로세스가 있으면, 방금 꺼낸 프로세스를 다시 큐에 넣는다.
- 큐에 있는 대기 프로세스들 중 우선순위가 더 높은 프로세스가 없으면, 방금 꺼낸 프로세스를 실행한다.
- 한 번 실행한 프로세스는 다시 큐에 넣지 않고 종료한다.
대기 큐에 있는 프로세스 중요도 배열 priorites,
몇 번째로 실행되는지 알고 싶은 프로세스 위치 location이 주어진다.
해당 프로세스가 몇 번째로 실행되는지 return하라.
[제한사항]
- 1 <= priorities 길이 <= 100
- 1 <= priorities[i] <= 9
- priorities[i]는 우선순위를 나타낸다. 숫자 클수록 우선순위 높다.
- 0 <= location <= (대기 큐 프로세스 수 - 1)
- 알고 싶은 프로세스가 priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현한다.
[풀이]
이거 우선순위 큐 문제다.
priorities에서 가장 큰 값을 찾아서, 빼고 할 때 빼는 횟수를 카운팅 한다.
빼는 그 값이 location에 위치한 프로세스이면, 현재 카운팅 변수를 반환하면 된다.
우선순위 큐에서 가장 큰 값을 찾는 데는 O(log N)이 걸린다.
이 과정을 N번 한다.
시간복잡도는 O(N logN) = O(100 log100) = O(100 * 2 * log10) = O(200 log10)
시간 충분하다. 1초 초과하지 않는다.
코드 1 - 오답
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int[] priorities, int location) {
PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>();
for(int i = 0; i < priorities.Length; i++)
{
maxHeap.Enqueue(-priorities[i], -i); // key = 우선순위, value = 인덱스
}
int count = 0;
for(int i = 0; i < priorities.Length; i++)
{
if(maxHeap.TryDequeue(out int priority, out int index))
{
count++;
if(index == -(location - 1))
return count;
}
}
}
}
최대 힙을 사용해 봤다.
프로그래머스 채점 환경의 C# 버전이 우선순위 큐가 없어서 에러가 난다.
그리고 우선순위 큐로 풀어도 이 코드로는 오답이 나온다.
코드2 - 정답
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int[] priorities, int location) {
int count = 0;
Queue<(int index, int priority)> queue = new Queue<(int index, int priority)>();
for(int i = 0; i < priorities.Length; i++)
{
queue.Enqueue((i, priorities[i]));
}
bool isSuccess = false;
while(queue.Count > 0)
{
(int index, int priority) p1 = queue.Dequeue();
foreach((int index, int priority) p2 in queue)
{
// 큐에 우선순위가 더 높은 프로세스가 있으면
if(p1.priority < p2.priority)
{
queue.Enqueue(p1);
isSuccess = true;
break;
}
else
isSuccess = false;
}
// 큐에 우선순위가 더 높은 프로세스가 없으면
if (!isSuccess)
{
// p1 프로세스를 실행한다
// 실행횟수 카운팅
count++;
// p1 프로세스의 인덱스가 location - 1이면
if(p1.index == location)
return count;
}
}
return count;
}
}
큐를 이용한 풀이다.
큐에 무조건 하나의 자료형만 들어갈 것이라고 생각했었다. 그런데 지난번에 풀었던 코드를 보니, 튜플도 넣을 수 있었다.
튜플로 인덱스와 우선순위를 저장하면 문제를 풀 수 있다.
코드3 - 오답
public int solution(int[] priorities, int location)
{
PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
for(int i = 0; i < priorities.Length; i++)
{
maxHeap.Enqueue(i, priorities[i]); // key = 인덱스, value = 우선순위
}
int count = 0;
for(int i = 0; i < priorities.Length; i++)
{
if(maxHeap.TryDequeue(out int index, out int priority))
{
count++;
if(index == location)
return count;
}
}
return count;
}최대 힙으로 풀 수 있는지 확인해봤는데, 일부 테스트케이스는 통과하지만, 통과하지 못하는 테스트케이스도 있다.
왜냐하면 최대 힙은 최댓값/최솟값을 찾아주지만, 나머지 원소들의 순서는 보장하지 않기 때문이다.
같은 우선순위인 프로세스가 있다면, 앞에 있는 프로세스가 먼저 실행되어야 하는데, 최대 힙은 순서가 보장되지 않기 때문에 오답이 나온다.
SortedSet도 최댓값/최솟값을 찾아주지만, 나머지 원소들의 순서는 보장하지 않기 때문에 같은 우선순위 프로세스 처리를 못하므로 오답이 나온다.
'자료구조, 코딩테스트 > 덱(Deque)' 카테고리의 다른 글
| [코딩테스트] BOJ 5430 - AC (실패) (0) | 2026.04.27 |
|---|---|
| [코딩테스트] BOJ 1021 - 회전하는 큐 (실패) (0) | 2026.04.26 |
| [코딩테스트] BOJ 10866 덱(실패) (0) | 2026.04.05 |
| [자료구조] 덱(Deque) (0) | 2026.04.05 |