[Baekjoon] 1966번 : 프린터 큐 (Python, 구현)

[Baekjoon] 1966번 : 프린터 큐 (Python, 구현)

 

목차

 

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

1966번: 프린터 큐

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 30840KB / 시간 76ms / 코드 길이 554B

 

본 문제는 FIFO 구조에서 중요도에 따른 문서 출력을 진행할 때, 특정 문서에 대한 출력 순서를 구하는 문제이다.

본 문제를 이해하는데 약간의 어려움이 있어 3번째 test를 기반으로 설명하면 다음과 같다.

 

6개의 문서가 주어지고 0번째 문서가 출력할 때가 몇 번째인지 알고싶은 것이다.

이때의 각 문서의 중요도는 1, 1, 9, 1, 1, 1이다.

 

0번째 문서	1번째 문서	2번째 문서	3번째 문서	4번째 문서	5번째 문서
1	1	9	1	1	1

 

여기서 첫 번째 문서의 중요도 보다 더 큰 중요도가 이후에 존재한다면 해당 문서는 뒤쪽으로 이동한다.

 

1번째 문서	2번째 문서	3번째 문서	4번째 문서	5번째 문서	0번째 문서
1	9	1	1	1	1

마찬가지의 순서로 생각하면 다음과 같이 순서가 이뤄진다.

2번째 문서	3번째 문서	4번째 문서	5번째 문서	0번째 문서	1번째 문서
9	1	1	1	1	1

3번째 문서	4번째 문서	5번째 문서	0번째 문서	1번째 문서
1	1	1	1	1

4번째 문서	5번째 문서	0번째 문서	1번째 문서
1	1	1	1

5번째 문서	0번째 문서	1번째 문서
1	1	1

0번째 문서	1번째 문서
1	1

 

이제 0번째 문서는 5번째에 대하여 출력되는 것을 확인할 수 있다.

 

필자는 해당 문서의 위치를 고정적으로 기억하기 위해 별도의 list를 구성하였고 각 조건에 따른 while문을 수행하도록 코드를 구현하였다.

 

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):

    n, m = map(int, input().split())
    l = list(map(int, input().split()))

    o = [[l[i], i] for i in range(n)]

    cnt = 0
    while o:
        now = o.pop(0)
        ck_F = False
        for i in o:
            if now[0] < i[0]:
                o.append(now)
                ck_F = True
                break

        if ck_F == True:
            continue
        elif ck_F == False:
            cnt += 1

        if m == now[1]:
            print(cnt)
            break

 

 

방법 2 - 메모리 30840KB / 시간 76ms / 코드 길이 459B

 

문제 1번이 복잡하게 얽혀있다고 생각할 수 있다.

이에 조금 더 간소화한 버전을 다음과 같이 준비했다.

문제 1에서는 for문을 돌며 큰 값이 존재하는지 판단했다면 여기서는 max를 통해 좀 더 빠른 정렬로 찾도록 한다.

그리고 이에 따른 index 값이 m과 같은지를 지속적으로 비교하며 그 값에 대한 count를 진행한다.

 

 

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    l = list(map(int, input().split()))
    idx = [i for i in range(n)]
    cnt = 0

    while l:
        if l[0] == max(l):
            cnt += 1
            if idx[0] == m:
                print(cnt)
                break
            l.pop(0)
            idx.pop(0)
        else:
            l.append(l.pop(0))
            idx.append(idx.pop(0))