프린터

• 1966과 동일한 문제.
• n 제한이 워낙 작아서 어떤 식으로 풀든지, 풀리기는 한다
• 시키는대로 계속 큐에서 로테이트 시키는 방식으로 시뮬레이션 하면서 처리한다면, 맨 앞의 문서가 가장 중요한 문서인지를 O(1)에 처리한다고 해도 (카운터 등을 써서..) 전체적으로 O(n^2)이 걸린다.
• O(|p|*n)에 푸는 방법을 생각해보자.
  • 중요도가 내 문서보다 높은 문서들은 당연히 먼저 출력될것이고, 찾아야 하는 것은 중요도가 내 문서와 같은 문서들 중에서 먼저 출력될 문서가 몇개인지이다. 이것을 계산하려면, 내 문서의 중요도가 p라면, 중요도가 p+1인 문서중에서 마지막으로 인쇄되는 것이 어떤 것인지 알아야 한다. 그러면 그 위치에서부터 내 문서 사이에 있는 중요도가 p인 문서들은 내 문서보다 앞에 출력된다.
  • 중요도가 p+1인 문서중에서 마지막으로 인쇄되는 것을 찾기 위해서는 중요도가 p+2인 문서중에서 마지막으로 인쇄되는 것이 어떤 것인지 알아야 한다. 그러면 그 위치에서부터 가장 멀리 있는 중요도가 p+1인 문서가 마지막으로 출력될것이다.
  • 따라서 이것을 역순으로 차례차례 처리하면, 처음에는 가장 중요도가 높은 문서중에서 가장 뒤에 있는 문서를 찾고 그 위치를 l에 저장한다. 그 다음 중요도가 높은 문서들 중에서 l부터 가장 먼 위치에 있는 문서를 찾고 그 위치를 다시 l에 저장한다. 이것을 반복하다가 찾아야 하는 문서의 중요도 p가 내 문서와 같아지면, l부터 내 문서의 위치까지 사이에 중요도가 p인 문서의 갯수를 모두 더한다.
• 위의 방법을 조금만 더 손보면 O(n)에도 가능하다
  • 위에서 O(|p|*n)이 걸린 이유는, 각 p마다, 'n개의 문서중에서 중요도가 p이면서 위치가 가장 먼 문서'를 찾기 위해서 n개의 문서를 매번 뒤졌어야 하기 때문인데, 처음에 미리 n개의 문서들을 p값에 따라서 분류해서 |p|개의 리스트로 분류해 놓으면, 각 이터레이션에서는 해당 리스트 안의 있는 문서들만 대상으로 위치가 가장 먼 문서를 찾으면 된다. 따라서 amortized 시간복잡도가 O(n)으로 줄어든다.
  • l번 위치의 문서에서 m번 위치의 문서까지 사이에 있는 문서의 수는 (m-l)%N 으로 쉽게 계산할수 있다.

"""Solution code for "Programmers 42587. 프린터".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42587
- Solution link: http://www.teferi.net/ps/problems/programmers/42587
"""


def solution(priorities, location):
    def dist_from_last_index(index):
        dist = index - last_index
        return dist if dist >= 0 else dist + len(priorities)
    
    priority = priorities[location]
    max_priority = max(priorities)
    indexes_by_priority = [[] for _ in range(max_priority + 1)]
    for i, p in enumerate(priorities):
        indexes_by_priority[p].append(i)
    last_index = 0
    answer = 0
    for p in range(max_priority, priority, -1):
        if not (indexes := indexes_by_priority[p]):
            continue
        answer += len(indexes)
        last_index = max(indexes, key=dist_from_last_index)
    target_dist = dist_from_last_index(location)
    answer += sum(1 for i in indexes_by_priority[priority]
                  if dist_from_last_index(i) <= target_dist)

    return answer