프로그래머스 - 프린터 (연결리스트)
이번 포스팅에서는 프로그래머스의 프린터 (연결리스트) 코딩테스트 연습 문제를 풀어봅니다.
문제 설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
- 인쇄 대기목록의 가장 앞에 있는 문서(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 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.
문제 풀이
먼저 입력된 priorities 리스트 location 위치를 표시하기 위해 요소 값을 [값, False]로 변경 합니다.
리스트의 pop과 append가 빈번한 구조 임으로 리스트를 deque로 변경 합니다.
location 위치의 False 값은 True로 교체 합니다.
from collections import deque
def solution(priorities, location):
priorities = deque(map(lambda x : [x, False], priorities)) # 리스트 요소의 값을 [값, False]로 교체
priorities[location][1] = True # location 위치의 값을 True로 교체
print(priorities)
solution([2, 1, 3, 2], 2)
deque([[2, False], [1, False], [3, True], [2, False]])
검색할 현재 목록을 빼서 now 변수에 저장하고 나머지 인쇄 대기목록에서 now 보다 중요도가 높은 문서가 한 개라도 존재하면 now 변수의 요소를 대기 목록의 가장 마지막으로 저장 합니다.
만일 조건이 위와 일치 하지 않으면 중요도가 더 높은 문서가 없음으로 now 문서를 인쇄하고 카운트를 증가 시킵니다. 만일 인쇄된 문서가 True이면 location의 위치 임으로 현재 문서가 몇번 째로 인쇄된 문서인지 확인 합니다.
입력 예제를 추가하여 코드로 구현 하면 아래와 같습니다.
from collections import deque
def solution(priorities, location):
priorities = deque(map(lambda x : [x, False], priorities)) # 리스트 요소의 값을 [값, False]로 교체
priorities[location][1] = True # location 위치의 값을 True 로 교체
answer = 0 # 출력된 문서 카운트
while priorities:
now = priorities.popleft() # 검색할 현재 목록
if sum(now[0] < p[0] for p in priorities): # 나머지 인쇄 대기목록에서 now 보다 중요도가 높은 문서가 한 개라도 존재하면
priorities.append(now) # 대기목록의 가장 마지막으로
else: # 그렇지 않다면 now 문서를 인쇄
answer += 1 # 인쇄된 문서 카운트 증가
if now[1]: # 인쇄된 문서가 location의 값이라면
return answer # 몇번째 인쇄된 문서 인지 출력
print(solution([2, 1, 3, 2], 2))
print(solution([1, 1, 9, 1, 1, 1], 0))
1
5
결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.
