[C#] 프로세스

프로그래머스 문제

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

풀이 후기

0. 잡담

문제 얘기는 아니고 요즘 코테하면서 느끼는 게 뭐냐면 해답이 눈에 보여도 ＇이런 식으로 구현 하는 게 맞나?＇ 싶은 게 좀 심해졌다. 원래도 게임 만들 때도 편한 구현 놔두고 과하게 최적화를 생각하면서 어려운 구현을 시도한다거나, int 배열로 처리해도 될 것을 비트 플래그로 바꾼다거나 그런 경향이 있긴 했지만, 시간 초과 맛을 보고나니 더 심해진 느낌.

1. 분석

진짜 하라는 대로 만들어도 되나? 트리를 만들어야 하나? 메모장으로 계산하다가 트리 + stack or queue는 아닌 거 같아서 포기. [1, 3, 1, 5] 이렇게 앞에 있던 프로세스가 뒤에 있는 프로세스보다 늦게 실행되는 케이스를 두고 이것저것 시도해보니 답이 딱히 안 보였다.

2. 최적화

가장 기초적인 구현은 진짜 하라는 대로 구현하면 될 것 같다. 배열 탐색하면서 뒤 배열에서 나보다 우선 된 순위가 있는지 확인하고 뒤로 넘기는 느낌은 O(n^2) 같아서 일단 보류했다.

내가 생각한 방법은, 한 번 훑어서 각 우선순위의 프로세스가 몇 개가 있는지 확인해서 배열에 저장하고 겸사겸사 큐에 넣는다. 큐를 탐색하면서 나보다 우선순위가 높은 프로세스 개수를 비교해서 없다면 해당 프로세스를 실행, 그리고 해당 우선순위 프로세스 개수를 차감한다. 이런 방식으로 굳이 뒤를 다시 탐색하지 않아도 숫자로만 카운팅 가능하게 만들어봤다. 대충 O(2n)가 아니라 O(n) 느낌 인 듯.

3. LINQ

그냥 LINQ 도배하고 싶었는데 많이 참았음.

4. 실행 결과

5. 코드

using System;
using System.Collections.Generic;

public class Solution {
    public struct Node{
        public int index;
        public int priority;

        public Node(int i, int p)
        {
            index = i;
            priority = p;
        }
    }

    public bool IsFirstPriorities(int n, int[] sub)
    {
        for (int i = n + 1; i < 10; i++)
        {
            if (sub[i] > 0)
            {
                return false;
            }
        }

        return true;
    }
    
    public int solution(int[] priorities, int location) {
        var len = priorities.Length;
        Queue<Node> nodes = new Queue<Node>();
        int[] subCount = new int[10];
        
        for(int i = 0; i < len; i++){
            var p = priorities[i];
            var node = new Node(i, p);
            nodes.Enqueue(node);
            subCount[p]++;
        }

        int count = 0;
        while (true)
        {
            var node = nodes.Dequeue();
            
            if (IsFirstPriorities(node.priority, subCount))
            {
                subCount[node.priority]--;
                count++;
                if (node.index == location)
                {
                    return count;
                }
            }
            else
            {
                nodes.Enqueue(node);
            }
        }
    }
}