[Silver III] 프린터 큐 - 1966

문제 링크

문제 해설

성능 요약
메모리: 11960 KB, 시간: 200 ms

분류
자료 구조, 구현, 큐, 시뮬레이션

문제 설명
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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번째로 인쇄되게 된다.

입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

문제 예제

풀이과정

1,0 [5]
4,2 [1,2,3,4]
6,0 [1,1,9,1,1,1]

앞에있는 숫자는 배열의 길이였고 두번째 있는 숫자는 찾아야하는 배열의 인덱스 번호입니다.
각각 찾아야하는 번호는 5와3 마지막으로 맨 앞에있는 1이였고
왼쪽부터 오른쪽으로 순서대로 가며 현재 있는 숫자보다 뒤에 큰 숫자가 있으면 뒤로 보내는 형식으로 구성하였습니다.

뒤로 보내면서 만약에 내가 찾아야할 인덱스면 배열의 길이만큼 더해주었고
만약에 내가 찾아야할 인덱스와 현재 인덱스가 동일하다면 answer에 넣어주고 반복문을 끝냈습니다.

나의 답안

const fs = require('fs').readFileSync('/dev/stdin');
const inputData = fs.toString().trim().split('\n');

class Stack {
	constructor(){
		this.queue = [];
	    this.answer = [];
	}
    push(arr) {
      this.queue.push(...arr);
    }
    find(idx) {
      const findEl = this.queue[idx];
      let findIdx = idx;
      let currentIdx = 0;
      let count = 0;
      while(this.queue.length > 0) {
        const current = this.queue.shift();
        const temp = this.queue.filter((el) => el > current);
        if(temp.length > 0) {
          this.queue.push(current);
          if(findIdx === currentIdx) {
            findIdx += this.queue.length;
          }
        } else {
          count++
          if(findIdx === currentIdx) {
            this.answer.push(count);
            return;
          }
        }
        currentIdx++
      };
    }
    clear() {
      this.queue = [];
    }
}

const Solved = (inputData) => {
  const [_ , ...data] = inputData;
  const stack = new Stack();
  for(let i = 0; i < data.length / 2; i++){
    const arr = data[(i * 2) + 1].split(' ').map(Number);
    const findIdx = Number(data[i * 2].split(' ')[1]);
    stack.push(arr);
    stack.find(findIdx);
    stack.clear();
  }
  console.log(stack.answer.join('\n'))
};
Solved(inputData);