17298. 오큰수

백준 17298. 오큰수

풀이과정

1차 시도

1. for문을 2중으로 사용하여 완전 탐색 -> O(n^2), 시간초과
2. for문을 한 번만 사용해야 함!

import sys

n, sequence = map(lambda x:x[:-1], sys.stdin.readlines())
sequence = list(map(int, sequence.split(' ')))

n = int(n)
answer = [-1]*n


for i in range(n):
    for j in range(i+1, n): # i보다 오른쪽에 있는 모든 수들 검사
        if sequence[i] < sequence[j]:
        	# squence[i] 보다 큰 수 나오면 answer 배열에 숫자 입력한 후 반복문 종료
            answer[i] = (sequence[j])
            break

print(' '.join(list(map(str, answer))))

최종

1. rest 라는 스택을 만듦
2. sequence[i] > sequence[i+1]일 때 i를 저장
   ( 자신의 바로 다음 원소가 자기보다 큰 수가 나오지 않은 숫자의 index를 저장 )
3. 나중에 sequence[i] < sequence[i+1] 인 상황이 오면 이 때 rest 스택에 있는 수들을 검사하여
   만약 rest안에 있는 index에 해당하는 숫자가 sequence[i+1] 보다 작다면 answer에 해당 index에 오큰수를 입력
   

import sys

n, sequence = map(lambda x:x[:-1], sys.stdin.readlines())
sequence = list(map(int, sequence.split(' ')))

n = int(n)
answer = [-1]*n
rest = []

for i in range(n-1):
    if (sequence[i] < sequence[i+1]):
        answer[i] = sequence[i+1]
        if (len(rest)):
            while (sequence[rest[-1]] < sequence[i+1]):
                answer[rest.pop()] = sequence[i+1];
                if (len(rest) == 0): break
    else:
        rest.append(i)

print(' '.join(list(map(str, answer))))