문제 설명
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
- 인쇄 대기목록의 가장 앞에 있는 문서(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 순으로 인쇄합니다.
내 풀이
def solution(priorities, location): que = [] arr = [[priorities[i], i] for i in range(len(priorities))] while arr: M = arr.index(sorted(arr,key= lambda x: (x[0],-arr.index(x)), reverse=True)[0]) que.append(arr.pop(M)) arr = arr[M:]+arr[:M] answer = que.index([priorities[location], location]) + 1 return answer
que에는 작업을 인쇄할 순서대로 담을 것이다.
arr에는 priorities에 저장돼 있는 순으로 priorities[i]와 그 index i를 range(len(priorities)) 범위에서 리스트 형태로 저장한다.
while문에서는 arr에 저장된 작업들을 인쇄할 순서대로 que에 옮겨서 배열할 것이다.
M은 arr를 (x[0], -arr.index(x))의 내림차순으로 정렬했을 때 가장 첫번째로 오게될 리스트가 arr에서 몇번째 인덱스인지를 구하는 것이다.
좀 더 자세히 설명하자면, arr의 인자 x의 0번째 요소 x[0]는 중요도를 의미한다.
즉, arr에서 중요도가 가장 큰 값의 index를 구하는데 만약에 중요도가 제일 큰 값이 여러개라면 그중에서 -arr.index(x)의 내림차순, 즉 arr.index(x)가 가장 작은 값의 index를 M에 저장하는 것이다.
M을 구하고 나면, arr에서 M번째 리스트를 pop해서 que에 담는다.
만약에 M번째 요소가 que에 담겼다는 것은 arr[:M]은 대기목록 맨 앞에서 꺼내져서 맨 뒤로 다시 넣어야 한다.
따라서 이 과정이 arr = arr[M:] + arr[:M]이다.
위에서 arr[M]를 이미 꺼냈기 때문에 arr[M+1:]이 아니라 arr[M:]이 맞다.
answer에는 요청한 문서가 몇번째로(인덱스가 몇이냐가 아니다) 인쇄되는 지를 알아야 하기 때문에 해당 인덱스를 구한 뒤에 1을 더해줘야 한다.
정확성 테스트: ~5.51ms / 10.3MB
다른 풀이
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 answer
직관적으로 이해하기 쉬운 코드이다.
queue에 priorities의 index와 우선순위를 튜플로 담는다.
while문에서 cur에는 queue의 첫번째 요소를 pop해 저장한다.
만약에 이 cur의 첫번째 요소인 우선순위가 queue에 들어있는 모든 요소 q의 우선순위보다 작다면 queue의 맨 끝에 append한다.
만약 아니라면 cur은 출력이 확정됐으므로 answer에 1을 더한다.
(answer에 1을 더하는 것을 if문 전에 함으로써 문서가 몇번째로 출력되는 지를 return 할 수 있다.)
if문에서 cur의 0번째 요소인 index값과 비교했을 때 location과 같다면 answer를 출력하고 아니라면 다시 while의 처음으로 돌아간다.
cur은 이미 출력이 확정됐으므로 다시 queue에 넣을 필요 없다.
정확성 테스트: ~1.05ms / 10.3MB
any()
if any(3 < a for a in [1, 2, 3, 4]): print("어떤 a는 3보다 크다") else: print("모든 a가 3보다 작다") ### 어떤 a는 3보다 크다
any 함수는 인자로 받은 반복 가능한 자료형(iterable) 중 하나라도 True면 True를 반환한다.
enumerator
print(list(enumerate(('a','b','c')))) ### [(0, 'a'), (1, 'b'), (2, 'c')]
순서가 있는 자료형의 index 번호와 해당 index의 요솟값을 객체로 return하는 함수이다.
이를 바로 출력하려면 list()와 같은 함수를 써야한다.
map() 함수로 등가를 만들자면
print(list(map(lambda x: (['a','b','c'].index(x), x), ['a','b','c'])))
위와 같다. 출력도 위와 동일하다.
