💡문제 분석 요약

• 입력
  • 첫 번째 줄: 테스트 케이스의 개수 T
  • 각 테스트 케이스는 두 줄로 이루어져 있다.
    • 첫 번째 줄: 문서의 개수 N과 목표 문서의 인덱스 M
    • 두 번째 줄: 각 문서의 중요도를 나타내는 정수 배열
• 출력:
  • 각 테스트 케이스마다 목표 문서가 몇 번째로 출력되는지를 출력
• 제약 조건:
  • 문서의 개수는 최대 100
  • 문서의 중요도는 1에서 9 사이의 정수

💡알고리즘 설계

절차

• 테스트 케이스를 반복 처리
• 각 테스트 케이스에 대해 다음과 같은 과정을 수행
  1. 큐에 문서 추가: 문서의 중요도를 큐에 저장
  2. 출력 과정:
     • 큐의 가장 앞에 있는 문서를 꺼냄
     • 이 문서의 중요도를 확인
     • 현재 큐에서 가장 높은 중요도를 가진 문서와 비교
     • 만약 꺼낸 문서의 중요도가 가장 높으면 출력 카운트를 증가시키고, 목표 문서가 출력되면 해당 카운트를 저장
     • 중요도가 낮으면 큐의 맨 뒤에 문서를 다시 추가
  3. 위치 업데이트: 목표 문서의 인덱스를 업데이트

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

// 배열 분해
let [n, ...arr] = input; 
// n은 테스트 수, 나머지는 테스트 정보

// 문자열 배열을 숫자 배열로 변환
arr = arr.map((item) => item.split(' ').map(Number));
let answer = '';

for (let i = 0; i < arr.length; i += 2) {
  let count = 0; // 출력된 문서의 수
  const priorities = arr[i + 1]; // 현재 테스트의 우선순위 배열
  let location = arr[i][1]; // 목표 문서의 초기 위치

  while (true) {
    // 현재 큐에서 가장 높은 우선순위를 가진 문서를 찾기
    const max = Math.max(...priorities);

    // 큐 앞에서 문서 하나 꺼내기
    const number = priorities.shift();

    // 꺼낸 문서의 중요도(number)가 최대 중요도(max) 비교
    if (number === max) {
      count++;

      // 목표 문서의 위치가 0일 경우
      if (location === 0) {
        //현재 출력된 문서 수(count)를 정답 배열에 추가
        answer += count + '\\n';
        break;
      }

    } else {
      // 꺼낸 문서의 중요도가 최대보다 낮으면 큐의 맨 뒤에 다시 추가
      priorities.push(number);
    }

    // 현재 문서의 위치가 0일 경우
    if (location === 0) {
      // 큐에서 마지막 문서로 위치 옮기기
      location = priorities.length - 1;

    } else {
      // 그렇지 않으면 단순히 1 감소
      location--;
    }
  }
}

console.log(answer.trim());

💡시간 복잡도

• 각 테스트 케이스마다 문서를 최대 N번 반복해서 확인할 수 있으므로 최악의 경우, O(N^2)의 시간복잡도를 가진다.
  • 여기서 N은 문서의 개수
  • 각 문서를 확인하고 출력하는 과정에서 문서의 위치를 변경해야 하기 때문이다.