[백준/BOJ] - 1966번 python 풀이 - deque, list 활용

---

Key Point

1. list를 통해 직관적으로 문제를 해결할 수 있지만 제한 시간이 2초이기에 다른 자료 구조를 사용하는 방법을 생각해보자.

2. max 내장 함수가 존재하는 자료 구조는 어떤 것이 있을까? list가 생각난다.

3. 시간 복잡도 면에서 유리한 자료 구조는 어떤 것이 있을까? deque가 있다.

 

즉, max를 구할때는 list 자료구조를 쓰고 핵심 동작을 구현할 때는 deque를 써보자!

 

※ 중요도 값이 같을 때는 어떤 값을 빼야할지 명확하지 않기 때문에 queue의 몇번째로 인쇄되었는지 궁금한 문서를 int형으로 넣지 않고 list로 넣어주었다.

ex(1 1 9 1 1 1) -> deque([ [1,1], 1, 9, 1, 1]) <- 다음과 같이 넣어줬음

max 값을 조사하기 위해 만든 list는 [1, 1, 9, 1, 1, 1] 로 넣어주었다.

 

 deque에서 어떠한 조건에 의해 pop 되는 값이 있으면 해당 값으로 list에서 찾아 remove method를 사용하여 list에서 그 해당하는 값을 제거해주었다.

 

알게 된 문법

list1 = [1, 2, 3]

list2 = list1 # 추후에 list1의 값을 변경하게 되면 list2도 덩달아 바뀌게 된다.

list2 = list1.copy() # 위의 문제점을 해결가능.

#queue에도 배열이 들어 갈 수 있으며 조회는 다음과 같이 한다.
from collections import deque

queue = deque([[1,2],3,4])

print(queue[0][0])
-> 1
print(queue[0][1])
-> 2

---

import sys
from collections import deque

N = int(sys.stdin.readline())

ord = 0
for i in range(N):
    cnt, idx = map(int,sys.stdin.readline().split())            
    #list                    
    lists1 = list(map(int,sys.stdin.readline().split()))
    temp = lists1[idx] 
    lists1[idx] = [lists1[idx],1]    
    #deque
    queue = deque(lists1.copy()) 
    lists1[idx] = temp    #list 2차원배열 제거
    maxi = max(lists1)

    while True:        
        #첫번째가 최댓값이 아니고 최댓값이 뽑아낼라하는거 보다 큼
        if type(queue[0]) == int:
            if queue[0] != maxi:
                queue.rotate(-1)                                                           
            else:                
                lists1.remove(queue[0]) #해당값 리스트에서 제거
                queue.popleft()
                maxi = max(lists1)                        
                ord+=1 #뽑아내기 카운트
        else: #타입이 리스트일경우 (핵심) 뽑아낼 경우
            if queue[0][0] != maxi and maxi > temp:
                queue.rotate(-1) 
            #마지막 핵심 뽑아내기    
            elif queue[0][0] == maxi and maxi == temp:
                ord+=1
                print(ord)
                ord = 0
                #lists1.clear()
                break    
            #첫번째가 최댓값인 경우 뽑아내기        
            else:
                lists1.remove(queue[0]) #해당값 리스트에서 제거
                queue.popleft()    
                maxi = max(lists1)                    
                ord+=1 #뽑아내기 카운트