문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예제 입력 1 복사
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
나의 풀이
let [n, ...arr] = require("fs").readFileSync('./input.txt').toString().trim().split("\n")
// 지금 arr는 '1 0' 이런 상태이므로, 1, 0 이렇게 잘라주고 넘버로 바꿔준다.
arr = arr.map((el) => el.split(' ').map(Number))
let answer = '';
for (let i = 0; i < arr.length; i += 2) {
// 왼쪽 - 문서의 개수 /오른쪽 - 알고싶은 문서 위치
// 둘째 줄 - 이 인덱스의 문서의 인쇄 순서 출력
solution(arr[i][0], arr[i][1], arr[i + 1])
}
function solution(num, idx, doc) {
// 인쇄 순서 카운트
let cnt = 0
while (true) {
// max에 doc 중에 제일 큰 수를 넣는다
const max = Math.max(...doc)
// doc에서 하나씩 빼서 number로 넣는다.
let number = doc.shift()
console.log('num>> ',number, ' doc>> ',doc)
// number가 max면
if (number === max) {
// 카운트 +1
cnt++
// 근데 idx가 0 이면(궁금한 수가 맨 앞에 오면
if (idx === 0) {
// 정답은 cnt하고 한 줄 띄기!
answer += cnt + '\n'
break
// 정답을 찾았으니 빠져나오기
}
} else {
// number가 max가 아니면 doc의 맨 끝으로 number를 보내준다!
doc.push(number)
}
// 위 과정을 거치고 나면 프린터의 위치가 하나씩 당겨지므로 idx가 0이면 마지막으로, 0이 아니었으면 하나 당겨준다.
if (idx === 0) {
idx = doc.length - 1
} else {
idx--
}
}
}
console.log(answer)
class로 Queue를 구현할까 하다가
그냥 이렇게 shift랑 push로 구현했당... Queue 만들어서 구현하는 것도 나중에 해보기로오~_~