1966번 프린터 큐
문제 출처 : 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
Author And Source
이 문제에 관하여(1966번 프린터 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wondang120/1966번-프린터-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)