백준1966 - 프린터 큐 Python

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

 

문제에서 입력은 여러 테스트케이스를 함께 주고, 하나의 테스트 케이스에는 출력 순서를 원하는 요소의 위치와, 요소 집합이 주어진다.

 

파이썬에서는 모듈로 queue를 제공한다고는 하지만, 모듈을 사용하지 않고 구현해보고 싶다는 생각에 사용하지 않았다.

 

접근한 풀이 방식은 다음과 같다.

출력을 원하는 위치(location) 0 | 그리고 요소 집합(arr) [1,1,9,1,1,1] 이 주어졌다고 한다면,

요소 집합을 내림차순으로 정렬하여 따로 저장하고, (이는 나가야 하는 숫자의 순서를 의미하는 배열로써 활용)

정렬된 배열의 첫 숫자를 우선 순위 값의 지시표로 활용하였다.

또 특정 위치에 존재하는 값을 따로 저장해두고, 집합에서의 특정 위치에 있는 값을 'a'로 변환했다.

 

예를 들면 아래와 같은 꼴인데, 이렇게 패싱하여 풀이하는 것이 다른 방식보다 쉬우리라는 생각이었다.

target_v = arr[location]
arr[location] = 'a'
# arr => ['a',1,9,1,1,1]

 

이후 아래와 같은 루프를 진행했다.

while (True) :
    # 맨앞 요소 꺼냄
    item = queue.pop(0)
    # 해당 값이 a와 같고 저장해둔 a의 값(target_v)가 현재 최댓값과 같다면 종료
    if item == 'a' and target_v == max_v :
      break
    # 해당 값이 최댓값과 같다면 queue에서 제외되는 경우므로 count ++
    # max_v 값도 새로 갱신
    elif item == max_v :
      count += 1
      sort_idx += 1
      max_v = sort[sort_idx]
    # 다른 경우 queue 뒤에 추가
    elif item != max_v :
      queue.append(item)
  return count

 

전체 소스 코드는 다음과 같다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
    
def solution (data) :
  data.pop(0)
  result = []
  for i,v in enumerate(data[::2]) :
    result.append(act(v, data[i*2+1]))
  print('\n'.join(map(str, result)))
  
def act (target_str, num_str) : 
  _, location = map(int ,target_str.split())
  queue = list(map(int, num_str.split()))
  sort = sorted(queue, reverse=True)
  sort_idx = 0
  max_v = sort[sort_idx]
  target_v = queue[location]
  queue[location] = 'a'
  count = 1

  while (True) :
    item = queue.pop(0)
    if item == 'a' and target_v == max_v :
      break
    elif item == max_v :
      count += 1
      sort_idx += 1
      max_v = sort[sort_idx]
    elif item != max_v :
      queue.append(item)
  return count

solution(input_data)