시뮬레이션 - 1 프린트 큐 (실버3)

 

문제

 

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

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

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

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

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

출력

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

예제 입력 1 복사

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1 복사

 

1
2
5

 

---

 

 문제 접근

 

이번 주차에서는 시뮬레이션 유형을 위주로 학습할 예정이다.

 

다른 알고리즘처럼 이론을 먼저 공부하지 않고 "구현"력 위주로 풀 수 있다는 생각을 하였다.

 

이후 문제를 해결하면서 구현력을 기르는것을 중점으로 학습하였다.

 

이번 문제의 핵심은 특정 문서의 출력 순서를 추적해야 한다는 점과

 

큐의 구조를 머리속에서 생각해 내었다는 점이다.

 

요구조건 2번째를 구현하기 위해 떠오른 생각은 "deque" 자료구조를 이용하면 손쉽게 풀 수 있다는 생각이 떠올랐다.

 

덱을 이전 문제해결에서 사용했던 내공 덕분이라고 생각한다.

 

순서를 출력하는 로직을 생각하기만 하면 구현은 쉬웠던 문제라고 생각한다.

 

---

소스 코드 

from collections import deque

t = int(input())
# 테스트 개수

for _ in range(t):

    n, m = map(int, input().split())
    # 중요도 1~9 이하의 정수
    # 중요도 중복 가능
    a = list(map(int, input().split()))

    for i in range(n):
        if i == m:
            temp = a[i]
            a[i] = (temp, 1)
        else:
            temp = a[i]
            a[i] = (temp, 0)

    d = deque(a)

    cnt = 1
    dap = {}

    while d:
        if d[0] == max(d, key=lambda x: x[0]):
            dap[cnt] = d.popleft()

            if dap[cnt][1] == 1:
                print(len(dap))
                break
            cnt += 1
        else:
            d.rotate(-1)

 

풀었던 키워드는

 

1. 덱 자료구조 이용

2. 답 리스트의 길이가 곧 출력 순서

3. max 의 key 활용

 

처음 제출 시 딕셔너리를 사용하게 된 이유는 key 값으로 순서를 지정하려 하였으나, 길이 출력이 출력순서인 것의 로직을 구현하면서 필요 없게 되었다. 이후 리스트를 사용하도록 소스코드를 수정하였다. 

 

# 키워드
# 덱 사용
# 튜플로 해당 문서 체크
# 해당 문서일 경우 답 리스트의 길이 = 순서

# 딕셔너리의 키값으로 출력하기 위해 딕셔너리로 하였지만 리스트로도 가능 할 듯


# 두번째 제출


t = int(input())
# 테스트 개수

for _ in range(t):

    n, m = map(int, input().split())
    # 중요도 1~9 이하의 정수
    # 중요도 중복 가능
    a = list(map(int, input().split()))

    for i in range(n):
        if i == m:
            temp = a[i]
            a[i] = (temp, 1)
        else:
            temp = a[i]
            a[i] = (temp, 0)
            # 추적할 문서 체크

    d = deque(a)

    cnt = 1
    dap = []

    while d:
        if d[0] == max(d, key=lambda x: x[0]):
            dap.append(d.popleft())

            if dap[cnt-1][1] == 1:
                print(len(dap))
                break

            cnt += 1
        else:
            d.rotate(-1)

 

---

 

다른 사람의 풀이

 

그리고 다른 사람의 소스코드를 비교 하여 보았다. 

 

# 다른 사람의 풀이

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    queue = deque(map(int, input().split()))
    queue = deque([(i, idx) for idx, i in enumerate(queue)])
    # 각 인덱스 값을 포함한 튜플을 이용하여 체크하는 방식이 다름

    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == M:
                print(count)
                # 그저 카운터 값을 출력하는 것도 방법
                break
            else:
                queue.popleft()
        else:
            # 덱의 메서드 로테이트를 사용하지 않고 append와 popleft 의 조합으로 rotate() 구현
            queue.append(queue.popleft())

 

주석에 내용대로 나의 소스코드와 비교하여 어떤 로직이 더 효율적인지 고민해 보며 코드를 해석하였다.

 

주요 차이점은 주석을 확인해 주세요