문제.
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO – First In First Out – 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 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 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력.
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예시
문제 해석
처음에 문제를 이해하기 어려울 수 있다. 하지만, 핵심은 큐(queue)를 통해 중요도가 높은 문서를 먼저 인쇄하는 과정이다.
1
3 0
1 3 2
1번 줄.
1개의 테스트가 입력된다.
2번 줄.
3개의 문서가 들어올 것이며 0번째 인덱스에 문서가 몇번째로 출력되는지 결과를 출력하라.
3번 줄.
0번째 문서의 중요도 1, 1번 째 문서 중요도 3, 2번째 문서 중요도 2
악필이지만 그림으로 설명하자면
0번째 인덱스가 언제 출력되는지 알고 싶은게 문제에 핵심이다. 큐를 통해 중요도를 파악하고 중요도가 낮으면 뒤로 이동하고 중요도가 가장 높은 순으로 출력을 하는 것이다.
본 문제의 출력 순서는 1번째 인덱스 문서, 2번째 인덱스 문서, 0번째 인덱스 문서 순서이다
그럼 우리가 문제에서 출력해야 하는 결과 값은 0번째 인덱스 문서의 출력 순서이기 때문에 3을 출력하는 것이 이 문제의 요구사항이다.
요구사항
- Queue 자료구조의 특징을 알고 있어야 한다.
- 내가 초점을 두고 있는 문서를 파악해야 한다.
- 가장 중요한 문서가 앞에 올 때까지 큐를 정렬해야 한다.
- 중요한 순서로 큐를 출력한다.
정답 코드 (Python)
## 궁금한 문서가 몇 번째로 출력되는지 계산하는 함수
def queue_print(queue):
# 첫 번째 문서가 중요도가 큰지 확인하는 함수
def check_importance(queue):
first = queue[0][1]
# 첫 번째 문서보다 중요한 문서가 있으면 뒤로 이동
for i in range(1, len(queue)):
if queue[i][1] > first:
pop_data = queue.pop(0)
queue.append(pop_data)
return False
return True
count = 1
while len(queue) != 0:
# 첫 번째 문서가 중요한 문서가 될 때까지 반복
for _ in range(len(queue)):
if check_importance(queue):
break
pop_data = queue.pop(0)
# 원하는 문서가 출력되면 몇 번째인지 출력
if pop_data[0] == True:
return count
else:
count += 1
testcase = int(input())
for _ in range(testcase):
N, M = map(int, input().split())
# 문서가 1개면 바로 출력
if N == 1:
importance = int(input())
print(1)
else:
importance = list(map(int, input().split()))
queue = []
# 궁금한 문서는 True, 나머지는 False로 구분
for i in range(N):
if i == M:
queue.append([True, importance[i]])
else:
queue.append([False, importance[i]])
print(queue_print(queue))채점 결과
