풀이
몇 번째로 나가는지 궁금한 대상을 index가 바뀌었을 때에도 어디에 위치해 있는지 어떤 방식으로 focusing 해낼 것인가가 관건이었다.
나는 그냥 정직하게 변수를 사용하여서 index의 번호를 직접 세도록 하면서 체크했다.
분명 관심 대상을 체크할 더 간단한 방법이 있을 텐데 도무지 생각이 나지 않았다.
import sys
from collections import deque
input = sys.stdin.readline
reps = int(input().rstrip())
for _ in range(reps):
N, M = map(int, input().split())
priority = deque(list(map(int, input().split())))
goal = priority[M]
processed = 0
curr = M
if len(set(priority)) == len(priority):
priority = sorted(priority, reverse=True)
print(priority.index(goal) + 1)
elif len(set(priority)) == 1:
print(M + 1)
else:
while max(priority) != goal:
if priority[0] == max(priority):
priority.popleft()
processed += 1
curr -= 1
else:
priority.rotate(-1)
curr -= 1
if curr == -1:
curr = len(priority) - 1
while curr != 0:
if priority[0] == goal:
priority.popleft()
processed += 1
curr -= 1
else:
priority.rotate(-1)
curr -= 1
print(processed + 1)발생 가능 상황 1: 모든 중요도가 다른 경우
-> 결국 중요도가 높은 것이 먼저 out 되기 때문에 역순으로 정렬하여 몇 번째 index에 위치해 있는지 확인하는 것과 같다.
발생 가능 상황 2: 모든 중요도가 같은 경우
-> 출구는 왼쪽만 사용하는 상황이기 때문에 몇 번째로 처리될지는 위치하고 있는 index와 같다.
발생 가능 상황 3: 그 외의 경우(중요도가 같거나 다른 경우)
-> 관심 대상보다 중요도가 높은 요소들은 관심이 없으므로 whlie 문을 활용하여 모두 처리한다.
+ 그 과정 중 현재 index를 가리키는 curr 변수가 out of range 에러를 내지 않도록 curr이 -1이 되면 맨 뒤 index를 가리키도록 한다.
-> 관심 대상이 큐 내에서 가장 높은 우선순위를 가질 때, 큐의 맨 앞으로 오도록 한다.
+ 관심 대상이 큐 내에서 가장 높은 우선순위를 가질 때에도 동일한 우선순위의 요소가 관심 대상보다 앞에 있을 수 있기 때문에 관심 대상이 맨 앞에 올 때까지 몇 개가 처리될 수 있는지 확인해야 한다.
-> 관심 대상이 맨 앞으로 왔다면, 지금까지 처리된 요소들의 개수에 1을 더해준다.
+ 1을 더해줌으로써 관심 대상은 몇 번째 처리 대상인지 나타낸다.
개선된 풀이
기록을 찾아보니 과거의 내가 이 문제를 풀었던 기록이 있었다.
기록된 코드를 봐보니 훨씬 깔끔하게 코드를 작성했었다.
물론 인터넷을 베껴서 작성했을 수도 있지만, 현재로써는 도움이 되는 부분이 있기에 개선된 풀이로 정리한다.
import sys
def printer():
reps = int(sys.stdin.readline().rstrip())
for _ in range(reps):
n, m = map(int, sys.stdin.readline().split())
priority = list(map(int, sys.stdin.readline().split()))
chosen = [None] * n
chosen[m] = "goal"
cnt = 0
while True:
if priority[0] == max(priority):
cnt += 1
priority.pop(0)
goal = chosen.pop(0)
if goal == "goal":
print(cnt)
break
else:
priority.append(priority.pop(0))
chosen.append(chosen.pop(0))
printer()chosen이라는 리스트를 통해 관심 대상이 어디에 있는지 체크하는 방식을 사용했다.
그렇게 함으로써 무슨 상황이 존재할 것인지 고려하지 않아도 되는 코드가 작성될 수 있었다.
chosen을 통해 goal이 어떤 index에 있는지 확인이 가능하고, 언제 큐에서 빠져나가는지 확인할 수가 있으므로
큐의 맨 앞에 있는 원소가 가장 높은 우선순위를 가진 원소일 때 제거를 하고 처리된 원소 수를 증가시킨다.
처리를 할 때, chosen 리스트에서 또한 pop을 시키는데 이때 chosen에서 빠져나온 원소가 goal이었다면 loop를 중단하고
지금까지 처리된 원소 수를 출력하는 방식이다.
goal이 아니었다면, 다시 pop했던 원소를 리스트의 맨 뒤로 집어넣고 loop를 계속한다.
