1966번: 프린터 큐

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

난이도: 실버 III

해당 문제는 Python 3으로 풀이하였습니다.

우선 문제에서 주어지는 테스트케이스의 수, N, M값을 변수로 받아오고, 문제 풀이에 필요한 변수들을 선언하겠습니다.

test = int(input())
for i in range(0, test):
    N, M = map(int, input().split())
    arr = []
    count = []
    for j in range(0, 10):
        count.append(0)
    remove = 9
    res = 0
    pos = 0
    find = 0

arr: 두 번째 줄에서 차례대로 주어질 N개 문서의 중요도를 담게 될 list입니다.
count: 중요도가 1부터 9까지의 정수임으로, 이들을 카운팅하기 위한 크기 10(0 ~ 9)의 list입니다.
remove: 중요도가 큰 순서대로 앞에서부터 하나씩 제거해 나갈 것인데, 현재 제거하고 있는 중요도의 값을 나타냅니다.
res: 해당 테스트케이스에서 최종적으로 출력될 결과값
pos: list를 순서대로 탐색하게 되는데 이 때 탐색하게 될 리스트 상의 좌표값
find: 최종적으로 res값을 찾은 경우 find값을 1로 설정하여 반복문에서 빠져나오게 됩니다.

    arr = list(map(int, input().split()))
    for j in range(0, N):
        count[arr[j]] += 1

반복문을 사용해서 변수를 입력받고, 앞서 언급했듯이 count list에 각각 문서의 중요도의 개수를 카운팅해줍니다.

Idea 1.

문제에서 언급하였듯이 자신의 뒤에 자신보다 중요도가 높은 문서가 있다면 순서가 맨 뒤로 skip될 것입니다.

이에 따라 list에서 해당 성분을 직접 맨 뒤로 옮겨주는 방법도 있겠지만, 그냥 pos값을 1만큼 증가시켜 다음 항목으로 넘어간 후, list의 끝에 도달하였을 때 다시 pos값을 0으로 돌아오게 해서 반복적으로 탐색하는 방식을 택한다면 더 구현이 용이할 것입니다.

Idea 2.

또한 이 탐색은, 우선순위값이 큰 문서가 무조건 먼저 인쇄됩니다.

e.g., 우선순위값이 4인 문서가 있다면, 우선순위값이 5 이상인 문서들이 모두 인쇄된 후에 인쇄될 수 있다는 것입니다.

이에 따라 count[] list에서 9부터 1까지 차례대로 문서들을 해결하면서 값을 카운팅해 나간다면 문제가 최종적으로 해결됩니다. 물론 결과값을 구한 이후에는 더이상 연산을 수행할 필요가 없으니 find값을 1로 설정하여 무한 loop에서 빠져나옵니다.

    while (find == 0):
        while (count[remove] == 0):
            remove -= 1

        if (remove == arr[pos]):
            if (count[remove] > 0):
                count[remove] -= 1
                res += 1

            if (pos == M):
                find = 1
        pos += 1
        pos %= N

    print(res)

앞서 언급했듯이, find값을 사용해서 무한 loop를 구현합니다.
현재 check해야 하는 우선순위값을 찾기 위해 count[remove]가 1 이상인 remove값까지 반복문으로 1씩 내려오며 찾습니다.
현재 check하고 있는 우선순위값과 현재 참조하고 있는 좌표에 해당하는 문서의 우선순위값이 같다면 해당 문서에 대해 remove처리 하며 res값을 counting해줍니다. 이 경우, 몇 번째로 출력될지 궁금한 문서(M)값과 같다면 find값을 1로 설정하여 최종적으로 무한루프를 빠져나오면 됩니다.
pos값을 증가시키며 반복문을 수행하다가 list 범위 밖으로 나가게 되는 경우에는 나머지 연산자를 사용해 다시 0으로 돌아오게 구현합니다. 이 방법을 통해 queue를 직접 구현하지 않고도 queue와 동일하게 작동하게 됩니다.
loop를 빠져나온 후 res값을 최종적으로 출력해주면 문제가 해결됩니다.

완성된 code

test = int(input())
for i in range(0, test):
    N, M = map(int, input().split())
    arr = []
    count = []
    for j in range(0, 10):
        count.append(0)
    remove = 9
    res = 0
    pos = 0
    find = 0

    arr = list(map(int, input().split()))
    for j in range(0, N):
        count[arr[j]] += 1

    while (find == 0):
        while (count[remove] == 0):
            remove -= 1

        if (remove == arr[pos]):
            if (count[remove] > 0):
                count[remove] -= 1
                res += 1

            if (pos == M):
                find = 1
        pos += 1
        pos %= N

    print(res)