[백준 1966번] 프린터 큐

https://www.acmicpc.net/problem/1966

 

=begin
1. 입력을 받는다. data도 받아서 queue에 저장
1-1. data[0]은 중요도, data[1]은 순서
2. 중요도를 기점으로 배치를 해야된다. 비교를 하면서
2-1. 처음에 비교를 해야됨 만약에 뒤에값보다 작으면 삭제 아니면 냅둠
2-2. map 라이브러리로 ㄱㄱ
=end


T = gets.chomp.to_i
T.times do |i|
  # 입력
  input = gets.chomp.split.map(&:to_i)
  n = input[0]
  m = input[1]
  document = gets.chomp.split.map(&:to_i)

  queue = []
  document.each.with_index do |num, j|
    queue.push([num, j])  # 배열을 직접 생성
  end

  answer = []
  while !queue.empty?
    pData = queue.first
    max_priority = queue.map { |q| q[0] }.max  # 현재 큐에서 가장 높은 중요도 찾기

    if pData[0] < max_priority
      queue.push(queue.shift)  # 중요도가 낮으면 뒤로 보냄
    else
      answer.push(queue.shift)  # 중요도가 가장 크면 처리
    end
  end

  # 출력 (몇 번째로 출력되는지 찾기)
  answer.each.with_index do |data_ex, k|
    if data_ex[1] == m
      puts k + 1
      break
    end
  end
end

 

문제 이해는 쉬웠지만, 구현이 까다로웠다. 예전에 풀었던 백준의 탑 문제와 비슷한 느낌이 들었다.

이 문제의 핵심은 중요도를 기준으로 정렬하여 원하는 인덱스가 몇 번째로 출력되는지를 파악하는 것이다. 하지만 중요도를 판별하려면 if 문, cnt 등의 여러 변수를 고려하며 순환해야 한다.

처음에는 루비에서 이를 간단하게 해결할 수 있는 라이브러리가 있을 거라고 생각했다. 즉, 리스트에서 가장 큰 요소를 찾는 기능만 있으면 복잡한 알고리즘을 구현할 필요가 없을 것 같았다. 결국 해당 기능을 찾아 활용했고, 문제를 해결할 수 있었다.