[백준 - C#] 1966번 프린터 큐

문제링크

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

문제

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다.
이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

문제풀이

처음 문제를 보고 중요도만 신경쓰다가 몇 번째로 인쇄되었는지 궁금한 문서에 대해서 신경을 쓰지못하였습니다.

그래서 큐를 입력 받을 때 중요도와 인덱스 순서를 같이 입력 받고 반복문을 계속 돌면서 몇 번째로 인쇄되었는지 구하였습니다.

 

result의 경우 몇 번째로 출력하는지 알기 위해 추가한 변수이고, count의 경우 max에서 다음 max값을 찾기 위해 전체 카운트를 가지고 있는 변수입니다.

 

그리고 문제를 제출 하였을 때 계속 시간초과가 났는데, queue와 count 배열을 초기화 하지 않아서 문제가 생겼었습니다.

 

이번 문제는 큐를 사용하며 여러 조건들을 잘 구현해내는 것이 힘들었습니다.

 

 

C# 코드 ( count 배열 )

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int t = int.Parse(reader.ReadLine());
 
    Queue<(int, int)> queue = new Queue<(int, int)>();
    int max = 0;
 
    for (int i = 0; i < t; i++)
    {
        int[] count = new int[10];
 
        string[] str = reader.ReadLine().Split();
        int n = int.Parse(str[0]); // 문서의 개수
        int m = int.Parse(str[1]); // Queue에서 몇 번째 놓여 있는지를 나타내는 정수
 
        int[] status = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
        int result = 0;
        queue.Clear();
 
        for (int j = 0; j < n; j++)
        {
            queue.Enqueue((status[j], j)); // (중요도, 인덱스순서)
            count[status[j]]++; // 같은 숫자에 대해서 카운트
        }
 
        max = queue.Max(o => o.Item1); // 중요도의 최대값을 구합니다.
 
        while (queue.Count > 0) // 큐가 1개 이상일 때까지 반복하며
        {
            // 중요도의 최대값이 큐의 값과 같다면
            if (max == queue.Peek().Item1)
            {
                // 입력받은 m과 인덱스 순서를 비교하여 같으면 출력하고 반복문 탈출
                if (queue.Peek().Item2 == m)
                {
                    writer.WriteLine($"{++result}");
                    break;
                }
 
                // 인덱스 순서가 같지않으면 pop하고 최종
                // result 값 ++
                // 같은 숫자 갯수 --
                int a = queue.Dequeue().Item1;
                result++;
                count[a]--;
 
                // 중요도를 max 부터 -- 하면서 다음 서치해야될 중요도를 찾습니다.
                if (count[a] == 0)
                {
                    while (count[max] == 0)
                        --max;
                }
            }
            else
            {
                queue.Enqueue(queue.Dequeue());
            }
        }
    }
 
    writer.Close();
    reader.Close();
}

public void Q1966()
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
    int t = int.Parse(reader.ReadLine());
    List<int> priority = new List<int>();
    int count = 0;
    for (int i = 0; i < t; i++)
    {
        string[] str = reader.ReadLine().Split();
        int n = int.Parse(str[0]); // 문서의 개수
        int m = int.Parse(str[1]); // Queue에서 몇 번째 놓여 있는지를 나타내는 정수
        int[] status = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
        Queue<(int, int)> queue = new Queue<(int, int)>();
        count = 0;
        priority.Clear();
        for (int j = 0; j < n; j++)
        {
            queue.Enqueue((status[j], j));
            priority.Add(status[j]);
        }
        priority.Sort();
        priority.Reverse();
        while (queue.Count > 0)
        {
            // 위치값과, 우선순위 값을 가져온 뒤 pop수행
            int value = queue.Peek().Item1;
            int location = queue.Peek().Item2;
            queue.Dequeue();
            // 값 비교
            if (priority[0] == value)
            {
                priority.RemoveAt(0);
                ++count;
                if (m == location)
                {
                    writer.WriteLine(count);
                    break;
                }
            }
            else
            {
                queue.Enqueue((value, location));
            }
        }
    }
    writer.Close();
    reader.Close();
}