문제

Programmers, 프로세스

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 프로세스가 대기열 큐에서 우선순위에 따라 실행될 때, 특정 위치의 프로세스가 언제 실행되는지 구하는 문제이다. 우선순위가 높은 프로세스가 나올 때까지 pop()과 push()를 반복하다가 현재 큐에서 우선순위가 가장 높고, 특정 위치의 프로세스라면 그때의 실행 순서를 답하면 된다. 삽입과 제거가 자주 발생하므로 LinkedList를 사용한다.
• Java의 경우 int[] arr같은 primitive 타입에 대한 역순 정렬을 제공하지 않으므로 오름차순 정렬 후 오른쪽 끝에서 시작하여 전체 길이에서 진행 방향만큼 차감해 주는 식으로 왼쪽부터 시작하는 인덱스를 구한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int>> q;
    for (int i = 0; i < priorities.size(); ++i)
        q.push({priorities[i], i});
    sort(priorities.begin(), priorities.end(), [](int a, int b) {
        return a > b;
    });
    int idx = 0;
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        if (cur.first == priorities[idx]) {
            ++idx;
            if (cur.second == location)
                return idx;
            continue;
        }
        q.push(cur);
    }
}

Java

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < priorities.length; ++i) 
            q.add(new int[]{priorities[i], i});
        Arrays.sort(priorities);
        int idx = priorities.length - 1;
        while (!q.isEmpty()) {
            var cur = q.poll();
            if (cur[0] == priorities[idx]) {
                if (cur[1] == location) {
                    return priorities.length - idx;
                }
                --idx;
            } else 
                q.add(cur);
        }        
        return 0;
    }
}