1966번 프린터 큐

·2021년 1월 26일
0

PS

목록 보기
6/42

문제 출처 : 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

profile
세상은 너무나도 커

0개의 댓글