.png)
문제 설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
- 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
- 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
- 그렇지 않으면 J를 인쇄합니다.
예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.
제한 사항
- 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
- 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
- location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.
입출력 예
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.
접근법
큐를 이용해 풀이가 가능한 문제이다.
파이썬에서 제공하는 deque() 함수는 리스트 자료구조에서 스택과 큐를
모두 구현할 수 있도록 도와준다.
append()와 pop()을 통해 스택의 후입선출 기능을 구현할 수 있고
popleft()와 append()를 통해 큐의 선입선출 기능을 구현할 수 있다.
이제 문제로 풀어보자
priorities 속 중요도에 따라 출력되는 순서를 예측해 볼 수 있는데
문제에서는 처음 주어진 값에서 요구하는 인덱스에 위치한 중요도의 문서가
몇번째로 출력되는지를 묻는 문제이다.
우선 주어진 리스트안 값을 단순하게 뽑아서 비교하고 다시 뒤에 넣는
큐 형태로 구현할 경우 구하고자 하는 값의 인덱스를 따라가기 힘들며
그로 인해 동일한 중요도가 많이 포하된 형태에서는 몇번째로 출력되는지
계산하기 힘들어진다.
그래서 자주 등장하는 enumerate()함수를 사용하는것이다.
해당 리스트에 인덱스와 그 인데스에 해당하는 값을 같이 반환해주는 아주
좋은 함수이다.
deque에 입력된 값중 가장 첫번째 값을 꺼낸 후
key 저장한다. 이는 그 뒤에 값과 비교하기 위함이다.
이때 popleft()를 통해 삭제와 반환을 통시에 진행하면
자동적으로 deque에 저장된 값의 첫번째가 다음값으로 변환된다.
문제에 주어진 조건에 따라 추출된 값이 주어진 값의 중요도 중 가장 크지
않다면 마지막 값으로 다시 넣어준다.
하지만 주어진 값의 중요도 중 가장 크거나 같다면 출력가능 여부
즉 출력되는 값의 개수를 체크할수 있도록 answer에 +1을 넣어준다.
또 동시에 출력 가능한 중요도의 인덱스가 location과 일치하는지도 확인해 본다.
location과 일치할 경우 바로 while문을 빠져나오도록 break문을 사용하고
출력된 값의 개수를 저장한 answer을 반환해주면 문제를 해결할 수 있다.
스택/큐에 대한 개념도 중요했지만 여기서 핵심은 출력되고 다시 입력되는
값들의 인덱스를 어떻게 부여하고 관리할 것인지라고 생각한다.
첫 시도에 해당 코드를 생각해 놓고 비슷하게 구현했지만
계속되는 실패도 다른 사람의 풀이를 참고하여 문제를 해결했다.
추가적으로 if d and max(d)[0] > key[0]:에 d를 빼먹을 경우
테스트에서 실패하게 된다.
단순히 d를 넣은것은 d 아무런 값도 없는 경우를 대비해서이다
d=[] 형태로만 있는 경우 False이고 d=[1]이 있는 경우는
True이다.
===========================================================
from collections import deque
def solution(priorities, location):
answer = 0
d = deque([(v,i) for i,v in enumerate(priorities)])
while len(d):
key = d.popleft()
if d and max(d)[0] > key[0]:
d.append(item)
else:
answer += 1
if key[1] == location:
break
return answer