[programmers] python 스택/큐 stack/queue 프린터

 

programmers.co.kr/learn/courses/30/lessons/42587?language=python3

코딩테스트 연습 - 프린터

 

 

< problem >

 

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

 

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

 

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

 

 

< constraint >

- 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
- 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
- location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

 

---

 

< example >

 

---

 

< solution ① > stack 활용

 

  - priorities 배열과 알고자 하는 위치를 매개변수로 입력받는 함수 구현

1. 우선순위가 가장 높은 값을 max_priority를 의미하는 max_pri 변수에 저장 
2. 가장 앞에 있는 우선순위를 스택에서 pop하여 변수 n에 저장

        - if 우선 순위가 max인 경우 answer+1

            - if location 값이 0인 경우 return answer

               else:  location-1

        - else: 스택 priorities 뒤에 n 추가

            - if location 값이 0인 경우 location = len(priorities)-1 // pop되었다가 스택 뒤에 추가되었기 때문

               else:  location-1

 

** location 변수는 입력받았을 때의 배열에서의 위치 의미

    - location이 0인 경우는 가장 앞에 있으니 출력됨을 의미

    - else: 아직 출력 전이므로 location-1 통해 한 칸 앞으로 이동 의미

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

<try>

    while문 조건에서 연산을 조금 줄이기 위해 while True:로 수정해보았는데 시간 차이는 크게 없었음

    오히려, 이전 방법이 더 빠른 경우도 있어 이 경우는 pass

 

---

 

< solution ② > deque 활용

 다른 코드 참고했을 때, 자료구조 덱을 사용하면 시간이 반으로 줄어든다고 해서 생각해봄

  <link> python deque 개념 참고 링크

    -  it-garden.tistory.com/146

    - appia.tistory.com/203

 

1. 덱 사용 전 import

2. 덱 함수 사용하여 덱 d 생성

3. deque가 비어있지 않은 경우 popleft( ) 사용하여 스택처럼 가장 왼쪽 값 pop 

    - 우선순위가 낮다면 append( ) 통해 오른쪽에 다시 추가

    - else: answer+1 한 후, pop한 값을 저장한 item index 1 값이 location과 같을 경우 return answer

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

 

---

 

< solution ③ > queue 활용 : 다른 사람 코드 풀이 참고

 

 

queue를 생성해준 후, 

어느 하나라도 True이면 return 하는 any ( ) 활용하여 훨씬 간단하게 함

이 방법까지는 생각 못 했는데 다른 분들 풀이를 참고하여 이해해봄

 

---

 

---

 

ⓒ ⓞ ⓜ ⓜ ⓔ ⓝ ⓣ

 

 

막상 deque 을 사용해보니 기존 코드의 실행 시간이 훨씬 빨라서 이유는 잘 모르겠음

파이썬으로 덱을 구현해보아 좋았음

코드를 줄이려고 해보았으나 생각보다 어려웠음