[알고리즘/자료구조] 1966 번 : 프린터 큐 - python

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

1966번: 프린터 큐

 

---

• 문제
• 소요시간: 32분 20초 실패 후 성공

---

• 설계하기(접근방법) 

1. 테스트 케이스를 입력받는다

2. 문서의 개수와 queue의 타겟인덱스를 입력받는다.

3. 중요도 리스트를 입력받는다

4. 알고리즘 해석

1) 중요도가 같은 경우가 있어서 처음 입력받는 타겟 인덱스 넘버의 위치를 관리해주어야 한다.

-> 문서가 출력되거나, 후순위로 밀린 경우 인덱스 위치 -1

-> 만약 후순위로 밀린 문서가 타겟넘버였다면 타겟넘버를 len(que())로 초기화 - (Ⅰ)

2) 문서를 출력하는 방법

->  현재 popleft() 즉 출력할 문서가 큐에서 최대 숫자 max(que)인경우 출력, cnt ++(출력순서)

else: popleft()후 append하여 후순위로 밀어버린다. (Ⅰ) 의 조건이 여기로 들어온다.

만약에 문서를 출력할 때 타겟인덱스가 [0] 즉 우리가 찾는 문서였다면 break 후 print(cnt)를 한다

 

 

 

 

---

• 코드(출력)

from collections import deque

t = int(input())


for i in range(t):
    n, target = map(int, input().split())     # 문서의 총 개수, 찾을 문서의 인덱스 위치
    que = deque(list(map(int, input().split())))  # 중요도제시
    cnt = 1
    while (que):
        if que[0] == max(que):  # 만약 popleft할 대상이 가장 큰 숫자라면
            if target == 0:  # 만약 타겟인덱스였다면
                print(cnt)
                break
            else:
                que.popleft()  # 타겟이 아니었다면 popleft()
                cnt += 1  # 카운트 ++
                target -= 1  # 타겟 넘버는 인덱스 위치 1 감소
        else:  # 더 큰 숫자가 있다면
            que.append(que.popleft())
            if target == 0:  # 타겟이 인덱스가 0이었다면
                target = len(que) - 1  # popleft()후 append 했으니 인덱스 넘버 끝으로 초기화
            else:
                target -= 1  # 타켓 인덱스 감소

---

• 얻어갈 부분

1. 타켓 넘버의 인덱스 위치를 이중배열로 풀려고 하다보니 너무 복잡해졌다.

해법 : 인덱스 넘버를 숫자로 선언해서 따로 관리하거나, 인덱스 넘버를 리스트로 따로 선언하여 같은 반복문 내에 넣는다

2. 인덱스가 계속 변하는 문제에 대해서 어떻게 접근해야될지 감을 잡았다