[C#] 백준 1966번 문제풀이

안녕하세요.

오늘은 백준 1966번 '프린터 큐' 문제 풀이를 진행해보겠습니다.

 

해당 문제는 새로운 프린터기의 소프트웨어 규칙에 맞추어 특정 종이가 몇번째로 출력되는지 알아내는 문제입니다.

새로운 프린터기의 소프트웨어 규칙은 다음과 같습니다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

바로 문제풀이에 들어가보겠습니다.

첫번째 입력으로는 T를 받아옵니다.

다음줄에 T만큼의 문제들을 풀기 위해 문서의 개수 N과 몇번째로 인쇄되었는지 궁금한 문서가 현재 몇번째 Queue에 놓여있는지 알아내는 정수 M을 받아옵니다.

그 다음줄에는 N만큼의 종이들의 중요도를 받아옵니다.

int T = int.Parse(Console.ReadLine());

for (int i = 0; i < T; i++)
{
    int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int[] priorities = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int N = input[0];
    int M = input[1];

 

인덱스와 중요도를 쌍으로 저장할 Queue를 선언해줍니다.

또한 받아온 종이의 중요도를 인덱스와 함께 Queue에 Enquque해줍니다.

    Queue<(int idx, int priority)> queue = new Queue<(int idx, int priority)>(); // 인덱스와 중요도를 쌍으로 큐에 저장
    for (int j = 0; j < N; j++) // 중요도를 하나씩 큐에 인덱스와 함께 저장
        queue.Enqueue((j, priorities[j]));

 

이제 문제에서 핵심이 되는 부분을 코딩해보겠습니다.

M번째 종이가 몇번째로 출력되는지를 알아내기 위한 변수 printCount를 선언해줍니다.

그리고, queue가 0이 될때까지 반복하는 while문도 만들어줍니다.

 

while문 안에서는, 먼저 queue에서 값 하나를 빼서 current변수에 넣어줍니다.

그 후에 LINQ를 사용하여 queue에 current값보다 하나라도 큰 값이 있는지 검사하고, true를 반환한다면 다시 queue의 맨 뒤로 넣어줍니다. 만약 true를 반환하지 않았다면, printCount를 하나 증가시켜줍니다. 이는 계속 리스트에 있는 값을 삭제하면서 자신이 찾고자 하는 값이 나왔을때 그 값을 몇번만에 찾았는지 알 수 있게 하기 위함입니다.

    int printCount = 0; // 프린트 카운트

    while (queue.Count > 0) // 프린트가 0이 될때까지
    {
        var current = queue.Dequeue(); // 하나 빼기
        if (queue.Any(x => x.priority >  current.priority)) // 뺀것보다 큰게 있으면
        {
            queue.Enqueue(current); // 뒤로가시고
        }
        else // 아니라면
        {
            printCount++; // 프린트 수 증가
            if (current.idx == M) // 만약 뺀게 찾으려는것과 같다면
            {
                Console.WriteLine(printCount); // 프린트 숫자 출력
                break; // 멈추기
            }
        }
    }

 

1966번의 정답코드는 여기까지입니다.

다음은 전체코드입니다.

internal class Program
{
    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        for (int i = 0; i < T; i++)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] priorities = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = input[0];
            int M = input[1];

            Queue<(int idx, int priority)> queue = new Queue<(int idx, int priority)>(); // 인덱스와 중요도를 쌍으로 큐에 저장
            for (int j = 0; j < N; j++) // 중요도를 하나씩 큐에 인덱스와 함께 저장
                queue.Enqueue((j, priorities[j]));

            int printCount = 0; // 프린트 카운트

            while (queue.Count > 0) // 프린트가 0이 될때까지
            {
                var current = queue.Dequeue(); // 하나 빼기
                if (queue.Any(x => x.priority >  current.priority)) // 뺀것보다 큰게 있으면
                {
                    queue.Enqueue(current); // 뒤로가시고
                }
                else // 아니라면
                {
                    printCount++; // 프린트 수 증가
                    if (current.idx == M) // 만약 뺀게 찾으려는것과 같다면
                    {
                        Console.WriteLine(printCount); // 프린트 숫자 출력
                        break; // 멈추기
                    }
                }
            }
        }
    }
}