[프로그래머스][C++] 프로세스
프로세스
문제 링크
분석
특정 문서가 몇 번째로 인쇄되는지를 구하는 문제입니다.
중요도가 높은 문서가 먼저 인쇄됩니다.
첫 번째 입출력 예를 보면 [2, 1, 3, 2]에서 2번 프로세스가 몇 번 째에 실행되는지 반환해야합니다.
0번 프로세스는 우선순위가 가장 높은 3이 아니며, 제일 높지 않으므로 나중에 실행되어야 합니다.
1번 프로세스는 우선순위가 가장 높은 3이 아니며, 제일 높지 않으므로 나중에 실행되어야 합니다.
2번 프로세스는 우선순위가 가장 높은 3이므로, 실행되어야 합니다.
2번 프로세스가 실행되는 순서를 구했으므로 반환합니다.
두 번째 입출력 예를 보면 [1, 1, 9, 1, 1, 1]에서 0번 프로세스가 몇 번 째에 실행되는지 반환해야합니다.
0번 프로세스는 우선순위가 가장 높은 9이 아니며, 제일 높지 않으므로 나중에 실행되어야 합니다.
1번 프로세스는 우선순위가 가장 높은 9이 아니며, 제일 높지 않으므로 나중에 실행되어야 합니다.
2번 프로세스는 우선순위가 가장 높은 9이므로, 실행되어야 합니다.
3번 프로세스는 현재 남은 것 중에서 가장 높은 1이므로, 실행되어야 합니다.
4번 프로세스는 현재 남은 것 중에서 가장 높은 1이므로, 실행되어야 합니다.
5번 프로세스는 현재 남은 것 중에서 가장 높은 1이므로, 실행되어야 합니다.
다시 0번 프로세스는 현재 남은 것 중에서 가장 높은 1이므로, 실행되어야 합니다.
0번 프로세스가 실행되는 순서를 구했으므로 반환합니다.
여기서 실행되지 않았던 프로세스는 큐 자료형을 사용하고, 나중에 다시 확인하기 위해서 가장 마지막 원소로 보냅니다.
현재 남은 프로세스 중에서 가장 높은 우선순위를 찾는 방법은 max_element함수를 사용하는 방법과 std::priority_queue를 사용하는 방법이 있습니다.
프로세스는 우선순위대로 원소가 하나씩 빠져나가므로, 큐를 사용합니다.
이때 큐는 인덱스의 정보 또한 가지고 있어야 하므로, pair를 사용합니다.
풀이
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> priorities, int location) {
int answer = 0;
// 가장 높은 우선순위를 순서대로(내림차순) 저장하는 큐
priority_queue<int> maxPQ(priorities.begin(), priorities.end());
// 우선순위와 인덱스를 저장하는 큐
queue<pair<int, int>> pairQueue;
// 우선순위와 인덱스를 저장하는 큐 초기화
for (int i = 0; i < priorities.size(); ++i)
{
pairQueue.push({priorities[i], i});
}
// 대기 중인 프로세스가 없을 때까지 반복
while (!pairQueue.empty())
{
// 현재 프로세스의 우선순위
int curPriority = pairQueue.front().first;
// 현재 프로세스의 인덱스
int curIndex = pairQueue.front().second;
// 현재 프로세스를 큐에서 제거
pairQueue.pop();
// 현재 프로세스가 남아있는 우선순위 중 가장 높은지 확인
if (curPriority == maxPQ.top())
{
// 프로세스 실행 횟수 증가
++answer;
// 몇 번 째로 실행되는지 알고싶은 프로세스였다면 반복문 탈출
if (curIndex == location)
{
break;
}
// 남아있는 프로세스 중 가장 높은 우선순위가 실행 됐으므로 제거
maxPQ.pop();
}
else
{
// 현재 프로세스의 우선순위가 가장 높지 않은 경우 큐의 맨 뒤로 이동
pairQueue.push({curPriority, curIndex});
}
}
return answer;
}
성능 요약
시간 복잡도는 $O(n^2)$입니다.
- 우선순위 큐 초기화 $O(n \ log \ n)$
- 큐를 초기화하는 반복문 $O(n)$
- 프로세스 실행 순서를 구하는 반복문 $O(n^2)$
- $O(n \ long \ n + n + n^2)$
공간 복잡도는 $O(n)$입니다.
- 우선순위 큐
maxPQ$O(n)$ - 큐
pairQueue$O(n)$ - $O(n + n)$
테스트 1 〉 통과 (0.01ms, 4.17MB)
테스트 2 〉 통과 (0.02ms, 3.66MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 3.68MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.02ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 4.14MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 3.68MB)
테스트 14 〉 통과 (0.01ms, 3.63MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 3.67MB)
테스트 18 〉 통과 (0.01ms, 3.63MB)
테스트 19 〉 통과 (0.02ms, 4.21MB)
테스트 20 〉 통과 (0.01ms, 4.2MB)
댓글남기기