[Lv.2] 프로세스 [프로그래머스_코딩테스트] [큐, 시뮬레이션] [25분]

🔍 문제 요약

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

프로그래머스

운영제제의 동작에서 프로세스들이 주어지고 해당 프로세스의 우선순위 배열 Priorities가 주어질 때 location에 해당하는 프로세스가 몇번째로 시행되는지 반환시키는 문제. (큐에 프로세스들을 다 집어넣고 순차적으로 돌리되 우선순위가 더 높은 프로세스가 큐 안에 있다면 꺼냈던 프로세스를 다시 집어넣고 그렇지 않으면 실행)

🧠 나의 접근 방식과 시행착오

15분 걸린 문제. 생각해보니 Data 구조체에서 Name은 쓰이지 않았다. IsTarget을 만들면서 지웠어야 하는 부분인데 남아있던듯함. 간단하게 생각해서 일단 zero-base로 동작하는 location의 데이터인지 Data 구조체에 Priority와 같이 매칭시켜서 캐시해두고, 해당 데이터들을 Queue에 집어 넣는다. 그리고 큐를 Dequeue시키면서 해당 큐 안에 더 큰 Priority가 있으면 다시 Enqueue시키는 과정을 반복하면 된다.

using System.Collections.Generic;

public class Solution
{
    public struct Data
    {
        public int Priority;

        public int Name;
        public bool IsTarget;

        public Data(int name, int priority, bool isTarget)
        {
            Name = name;
            Priority = priority;
            IsTarget = isTarget;
        }
    }
    
    /// <summary>
    /// 프로세스
    /// https://school.programmers.co.kr/learn/courses/30/lessons/42587
    /// </summary>
    public int solution(int[] priorities, int location)
    {
        // location은 zero-base
        Queue<Data> dataQueue = new Queue<Data>();

        for (int i = 0; i < priorities.Length; i++)
        {
            dataQueue.Enqueue(new Data(i, priorities[i], i == location));
        }

        int count = 0;

        while (dataQueue.Count > 0)
        {
            var isExecute = true;
            Data data = dataQueue.Dequeue();

            // 더 우선순위 높은 데이터가 있어서 뒤로 다시 넣기
            foreach (var tData in dataQueue)
            {
                if (data.Priority < tData.Priority)
                {
                    isExecute = false;
                    break;
                }
            }

            if (!isExecute)
            {
                dataQueue.Enqueue(data);
                continue;
            }

            count++;

            if (data.IsTarget)
            {
                break;
            }
        }
        
        return count;
    }
}

✅ 풀이 코드

Linq를 쓴 좀 더 간단한 방식의 코드가 있다. Linq가 성능에 별로 좋지 않다는 점이 있어서 그렇게 활용하고 있지는 않음. 추가로 Name을 정리하는 것은 위에서 이야기한 부분이지만 나중의 디버깅을 위해서 냅둬도 큰 상관 없을 듯 함.

if (dataQueue.Any(x => x.Priority > data.Priority))

🔄 정리

우선순위 큐라는 것이 C# 7.0+에 나왔기 때문에 해당 자료구조를 사용하면 더 깔끔한 방식이 될 듯 하긴 하다. 그렇기 전에 큐 사용에 대해서 간단히 공부해볼 수 있는 문제가 될 듯 하다.