📩 -->문제설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
- 인쇄 대기목록의 가장 앞에 있는 문서(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로 표현합니다.
입출력 예
| priorities | location | return |
|---|---|---|
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
💡 solution(사용언어: python)
from collections import deque
def solution(priorities, location):
dq = deque(priorities)
rank = deque(list(zip(priorities, range(len(priorities)))))
result=[]
while len(dq)!=0:
if dq[0] < max(dq):
dq.append(dq.popleft())
rank.append(rank.popleft())
else:
dq.popleft()
result.append(rank.popleft())
return result.index((priorities[location],location))+1
👉 설명
이 문제는 자료구조 중 하나인 큐를 이용했다. 자료구조에 관해서는 추후 포스팅 할 '계획'은 있다...
- 먼저 우선순위를 dq에 담아준다.
- rank에는 우선순위와 인덱스를 zip을 통해 리스트 형태로 담아 주었다.
- dq 에서 순서대로 값을 뽑고 그 값이 max(dq)보다 작다면 dq.popleft()를 통해 그 값을 dq에서 삭제한 후 제일 뒤로 넣어주었다.
- 마찬가지로 rank에도 같은 과정이 진행된다.
- 만약 dq에서 뽑은 값이 가장 큰 순서라면 dq에서 지우기만 하고 result에 해당 rank 값을 넣어준다.
- result.index()를 통해 원하는 값을 리턴해준다.
결과
다른 풀이
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answerif any를 쓰면서 값을 비교한게 특징이다!
🌈 느낀 점
알고리즘이나 자료구조를 이용해서 푸는 문제들이 꽤 있어서 공부해야 할 필요성을 많이 느꼈다!
출처: 프로그래머스
오류가 있으면 댓글 달아주세요🙂
