[백준] 1966번

그녕·2023년 3월 21일
0

알고리즘 문제 풀이

목록 보기
21/29
post-thumbnail

백준 1966번

이 문제는 생각보다 이해도 잘 안되고 어려워서 시간이 꽤 걸렸고 못 풀었다.. 풀이 이해하는데도 시간이 좀 걸렸던 문제이다.

🍀내 풀이🍀

일단 queue에 중요도를 넣어주기 위해서 list로 만들어준다음에 deque에 넣어주었다.
계속 돌아가야하므로 while queue 반복문을 써주었고, 최댓값을 비교해줘야해서 best로 먼저 설정해준다. 이거를 먼저 설정안해주니깐 오류가 났다...바로 앞에 front 애를 빼주고 그 순번을 -1 해주기 때문에 만약에 제일 앞에 최댓값이 있게 되면 오류가 날수밖에 없다... 하아,,, 어려운 녀석....😢

그 다음에 뽑아줬으면 조건을 걸어줘야한다. 뽑은 걔가 가장 큰 최댓값이라면 cnt에 1을 더해주면 된다. 하지만 이때!! 주의 해야할 점이 만약 젤 앞에 있는 0번째를 구하는 문제였다면? 순서를 1빼주기 때문에 (앞당겨지기 때문에) -1인 음수가 된다. 그래서 이때는 젤 최댓값이 젤 앞에 있는 애였는데 또 걔가 우리가 구하는 그 녀석이라면 cnt를 출력해주고 break 해주면 된다!!

하지만 뽑은 애가 최댓값이 아니라면 ?? 우리는 그 뽑은 녀석을 젤 뒤에 붙여줘야한다. 그래서 append(front)를 해준다. 근데 또 아까처럼 걔가 우리가 찾는 그 녀석 0번째라면 ??!! 순서를 0번째에서 -1번째가 되는데 음수 순위가 되면 안되니깐 전체 길이에서 1을 빼주면 그 순서가 나온다. 즉 6개가 있으면 제일 앞에 있는 애가 뒤로 밀리면서 인덱스가 5가 되기 때문이다. 이렇게 계속 반복문을 돌아주면 끝!

근데 이걸 혼자 어떻게 생각해내나..... 하아....... 담에 다시 풀어보자,,,힝 ಥ_ಥ

🍀내 코드🍀

from collections import deque
import sys
input=sys.stdin.readline
T=int(input())

for _ in range(T):
    N,M=map(int,input().split())
    queue=deque(list(map(int,input().split())))
    cnt=0
    while queue:
        best=max(queue)
        front=queue.popleft()
        M-=1
        if front==best:
            cnt+=1
            if M<0:
                print(cnt)
                break
        else:
            queue.append(front)
            if M<0:
                M=len(queue)-1

0개의 댓글