사용자 도구

사이트 도구


ps:problems:programmers:42587

프린터

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42587
출처프로그래머스
문제 번호42587
문제명프린터
레벨Level 2
분류

애드혹

시간복잡도O(plogn)
인풋사이즈p<=9, n<=100
사용한 언어Python
해결날짜2021/05/04
태그

고득점 Kit - 스택/큐

풀이

  • 시키는대로 계속 큐에서 로테이트 시키는 방식으로 처리한다면, 맨 앞의 문서가 가장 중요한 문서인지를 O(1)에 처리한다고 해도 (카운터 등을 써서..) 전체적으로 O(n^2)이 걸린다.
  • O(n) 솔루션이 있을거 같아서 고민해봤지만 떠올리는 데에는 실패.
  • 대신 O(p*n)은 가능하다.
  • 중요도가 내 문서보다 높은 문서들은 당연히 먼저 출력될것이고, 찾아야 하는 것은 중요도가 내 문서와 같은 문서들 중에서 먼저 출력될 문서가 몇개인지 이다. 이것을 계산하려면, 내 문서의 중요도가 p라면, 중요도가 p+1인 문서중에서 마지막으로 인쇄되는 것이 어떤 것인지 알아야 한다. 그러면 그 위치에서부터 내 문서 사이에 있는 중요도가 p인 문서들은 내 문서보다 앞에 출력된다.
  • 중요도가 p+1인 문서중에서 마지막으로 인쇄되는 것을 찾기 위해서는 중요도가 p+2인 문서중에서 마지막으로 인쇄되는 것이 어떤 것인지 알아야 한다. 그러면 그 위치에서부터 가장 멀리 있는 중요도가 p+1인 문서가 마지막으로 출력될것이다.
  • 따라서 이것을 역순으로 차례차례 처리하면, 처음에는 가장 중요도가 높은 문서중에서 가장 뒤에 있는 문서를 찾고 그 위치를 l에 저장한다. 그 다음 중요도가 높은 문서들 중에서 l부터 가장 먼 위치에 있는 문서를 찾고 그 위치를 다시 l에 저장한다. 이것을 반복하다가 찾아야 하는 문서의 중요도 p가 내 문서와 같아지면, l부터 내 문서의 위치까지 사이에 중요도가 p인 문서의 갯수를 모두 더한다.
  • 각 p에 대해서 등장하는 인덱스들을 미리 저장해놓고, 특정 p의 마지막 위치를 바이너리 서치로 찾는다면 O(plogn)도 가능하다. 구현은 해보지는 않았다.

코드

"""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):
    priority = priorities[location]
    for p in range(9, priority, -1):
        ind = max((i for i, x in enumerate(priorities) if x == p), default=0)
        location -= ind
        priorities = priorities[ind:] + priorities[:ind]
    location %= len(priorities)
    return sum(1 for i, x in enumerate(priorities)
               if (x, -i) >= (priority, -location))

토론

댓글을 입력하세요:
Q V G M C
 
ps/problems/programmers/42587.txt · 마지막으로 수정됨: 2021/05/21 07:19 저자 teferi