문제 출처 : https://www.acmicpc.net/problem/1966
상당히 시간이 오래 걸린 문제. 그 이유는 무엇인고 하니 그냥 간단하게 index에 따른 새로운 배열을 만들어주고 원형 큐로 처리해주면 풀릴 것을 어떤 규칙, 수식을 찾아서 더 멋지고 효과적인 방식을 추구하려다 보니 쓸데없이 오래 걸린 문제
이게 보니까 num[0] 뒤에 더 큰 게 있으면 출력이 안되네 그러면 num[0]보다 큰 값들을 모두 pop해주면 되겠다. 이 때 num[0]보다 큰 값들 중에서 가장 큰 index를 마지막으로 출력한 이후부터 다시 arr[0]와 동일한 값을 가진 요소들이 출력되기 시작하니까...
import sys
T = int(sys.stdin.readline().rstrip("\n"))
for _ in range(T) :
N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
target, result = num[M], 0
min_n,idx = float('inf'), 0
same_i = []
#IN Bigger than target, min is last pop
#After that same with target num pop
for n in range(N) :
if num[n] > target :
if min_n>num[n] :
min_n = num[n]
idx = n
elif min_n == num[n] :
idx = max(idx,n)
result+=1
elif n!=M and (num[n]==target) :
same_i.append(n)
for m in same_i :
if idx<M :
if (idx<m) and (m<M) : result+=1
if M < idx :
if not (M<m and m<idx) : result+=1
print(result+1)
결과는 실패!
import sys
from collections import deque
T = int(sys.stdin.readline().rstrip("\n"))
for _ in range(T) :
N, M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
result = 0
new = deque([])
for i,n in enumerate(num) :
new.append([i,n])
while True:
if new[0][1] == max(new, key = lambda x: x[1])[1] :
if new[0][0] == M :
break
new.popleft()
result+=1
else :
new.append(new.popleft())
print(result+1)
브루트 포스?
흠... 예전에 교수님께서 while True문은 결국 무한반복문이기 때문에 사실 좋은 건 아니라고 해서 지양하는 편이였는데 이 문제는 너무 빡침... 그래서 그냥 해결이나 하고 싶었다. 나중에 기회가 된다면 조금 더 발전시켜서 다시 풀어보도록 하자... 너 때문에 너무 힘들었어
( list의 pop(0)를 쓰면 시간복잡도가 조금이나마 커질것같아서 deque를 썼는데 근소하게나마 list가 더 빠르네...?)
lisiant01 iougou03