[BOJ] 1966 : 프린터 큐 [자료구조](Python)

문제 링크

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

1966번: 프린터 큐

소스 코드

c = int(input())
for i in range(c):
    n,m = map(int,input().split())
    # 입력 리스트, 입력 당시의 순서를 기록할 리스트
    my_list = list(map(int,input().split()))
    order_list = [x for x in range(len(my_list))]
    
    cnt = 0
    while True:
        # 맨 앞의 원소가 가장 클 때
        if my_list[0] >= max(my_list):
            cnt += 1
            # m번째 원소가 맞다면 스탑
            if order_list[0] == m:
                break
            else: # 그렇지 않은 경우 계속 반복
                my_list = my_list[1:]
                order_list = order_list[1:]
        # 맨 앞의 원소가 가장 크지는 않은 경우
        else:
            my_list = my_list[1:] + my_list[:1]
            order_list = order_list[1:] + order_list[:1]
    print(cnt)

 

해설

• 단순 구현

이 문제를 풀기 위해선 원래 입력으로 받은 리스트에서의 인덱스값을 기억하고 있어야 합니다.

제 풀이처럼 하지 않고 리스트의 원소를 튜플로 바꿔주거나 딕셔너리로 기억하게 하는 방법도 있을 것 같습니다.

 

우선 기존에 입력 받은 리스트의 인덱스 번호를 order_list 에 저장해줍니다.

반복문에서 처리하게 되는 리스트의 원소가 기존 m번째 원소가 맞는지 확인하기 위함입니다.

 

맨 앞의 원소가 리스트 내의 최댓값이 맞다면 출력 횟수를 cnt에 반영합니다.

이때 기존 리스트의 m번째 원소를 출력한 것이 맞는지 확인하여 맞다면 풀이를 종료하고,

그렇지 않다면 맨 앞의 원소를 뒤로 보냅니다.

기존 리스트의 인덱스 번호를 담고 있는 order_list에도 동일한 작업을 해줍니다.

 

만약 리스트의 맨 앞 원소가 가장 큰 것이 아니라면 어떤 처리도 하지 않고 맨 뒤로 보내줘야 합니다.

마찬가지로 기존 리스트의 인덱스 번호를 담고 있는 order_list의 맨 앞 원소도 뒤로 보내줍니다.

 

#BOJ #백준 #알고리즘 #Python #파이썬