인쇄기
문제 연결
프로그램 제작자
코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
Programmer.co.kr
문제 설명
일반적인 프린터는 인쇄 요청을 받은 순서대로 인쇄합니다. 중요한 문서는 나중에 인쇄할 수 있습니다. 이를 보완하기 위해 중요한 문서를 먼저 출력하는 프린터를 개발했습니다. 새로 개발된 이 프린터는 다음과 같은 방식으로 인쇄를 수행합니다.
1. 인쇄 대기열의 맨 앞에 있는 문서( J )를 대기열에서 제거합니다.
2. 나머지 인쇄 대기열에 J보다 우선 순위가 높은 문서가 하나라도 있으면 J가 대기열의 끝에 배치됩니다.
3. 그렇지 않으면 J를 누릅니다.
예를 들어 4개의 문서( A, B, C, D )가 인쇄 대기 중이고 우선 순위가 2-1-3-2인 경우 CDAB 순서로 인쇄됩니다.
요청한 문서가 몇 번 인쇄되었는지 알고 싶습니다. 위의 예에서 C가 먼저 인쇄되고 A가 세 번째로 인쇄됩니다.
우선 순위, 현재 큐에 있는 문서의 중요도를 포함하는 배열, 인쇄 요청된 문서의 위치를 나타내는 위치가 매개변수로 주어지면 인쇄 요청된 문서의 개수가 매개변수로 주어집니다. 인쇄되면 리턴할 해결 함수를 작성하십시오.
제한
- 현재 대기자 명단에 있는 문서는 1개 이상 100개 이하입니다.
- 인쇄 작업의 중요도는 1에서 9까지의 척도로 표현되며 숫자가 높을수록 중요도가 높음을 나타냅니다.
- 위치는 0(현재 대기열에 있는 작업 수 – 1) 이상의 값을 가지며 대기열의 맨 위에 있으면 0, 두 번째 스탠드에 있으면 1로 표현합니다.
I/O 예시
| 우선 순위 | 위치 | 돌려 주다 |
| (2, 1, 3, 2) | 2 | 하나 |
| (1, 1, 9, 1, 1, 1) | 0 | 5 |
I/O 예시 설명
I/O 예제 #1
문제의 예와 동일합니다.
I/O 예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기 중이고 우선 순위가 1-1-9-1-1-1이므로 CDEFAB 순서로 인쇄됩니다.
해산 과정
1. 인쇄 요청 문서의 순환 번호와 대기 목록에 있는 문서의 열거 기능을 사용하여 색인 및 중요도를 생성하고 대기열에 넣습니다. 큐는 컬렉션 모듈에서 dequq를 사용합니다.
2. 대기열이 존재하는 동안 while 루프를 반환합니다.
3. 첫 번째 문서보다 중요도가 높은 문서가 있으면 popleft 하여 뒤에 붙입니다.
4. 첫 번째 문서보다 중요도가 높은 문서가 없으면 순서대로 1씩 증가하여 인쇄됩니다.
5. 위치와 인덱스를 비교하고 요청된 문서의 차례가 되면 while 루프가 종료되고 차례가 반환됩니다.
전송 코드
from collections import deque
def solution(priorities, location):
# 요청한 문서가 인쇄되는 순번
turn = 0
# 대기목록에 있는 문서의 인덱스 i와 중요도 p
queue = deque(( (p, i) for i, p in enumerate(priorities) ))
# queue에 값이 존재하지 않을때 까지 while loop
while queue:
# 맨 앞 문서보다 중요도가 더 큰 문서가 있다면 맨 뒤로 보낸다.
if queue(0)(0) < max(queue)(0):
queue.append(queue.popleft())
# 중요도가 가장 높은 문서를 출력한다.
else:
# 출력 될 때 마다 차례를 1씩 증가시킨다.
turn += 1
# 내가 요청한 문서가 출력되면 인쇄를 멈추고 차례를 반환한다.
if location == queue.popleft()(1):
break
return turn
다른 솔루션
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
any() – 있으면 참
– 모든 (( 거짓, 거짓, 거짓 )) # 거짓
– any((거짓, 거짓, 참)) # 참all() – 모든 것이 사실이어야 합니다.
– 모두(( 거짓, 거짓, 참 )) # 거짓
– all(( 참, 참, 참 )) # 참
이 코드는 any를 사용하여 불필요한 프로세스를 생략한 것으로 유명합니다. 그러나 pop(index)의 시간복잡도는 O(N)이므로 시간복잡도를 O(1)로 줄이기 위해서는 popleft()를 사용하는 것이 더 효과적일 것이다.
