Check Point !
( 해당사항 ✓체크 )

막힘 없이 수월하게 풀린 문제인가?

1시간이내로 풀렸던 문제인가? ✅

1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

시간을 써도 도무지 풀 수 없는 문제인가?

솔루션을 찾아봤는가? ✅

난이도 체감

최상

상

중

하 ✅ (실3)

<이해도>

완벽히 이해 ✅

다소 헷갈리는 부분들이 있음

이해 못함

<덧붙일 말>
구현에서는 정렬을 이용해서 해결하는법이 많던데
비슷하지만 여기서는 정렬을 안사용하고 풀었다.
하지만 풀이 2방식의 방법도 이해하고 풀어보자

문제

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

풀이 1

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    nss = list(map(int,iㅁnput().split()))
    
    arr = []
    enm = []
    
    for i,nx in enumerate(nss): 
        enm.append((nx,i+1)) 
    
    k = enm[m][1]
    
    
    while enm:
        for i in range(1,len(enm)):
            if enm[0][0] < enm[i][0]:
                enm.append(enm.pop(0))
                break
        else:    
            arr.append(enm.pop(0))
    
    cnt = 0
    for x,y in arr:
        cnt += 1
        if y == k:
            break
    print(cnt)
            
     

from collections import deque

t = int(input())

for _ in range(t):
    n,m = map(int, input().split())
    s = list(map(int, input().split()))
    q = deque()
    
    for i,x in enumerate(s):
        q.append((i,x))
    
    s.sort()
    cnt = 0 
    
    while q:
        i,x = q.popleft()
        if x == s[-1]:
            s.pop()
            cnt += 1
            if i == m:
                print(cnt)
                break
        else:
            q.append((i,x))