17298

날짜 : 2023. 06. 01

사용 언어 : python

 

문제

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

 

 

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
ans = [-1] * n
stack = list()
stack.append(0)
i = 1
while i < n:
    now = a[i]  # 현재 숫자
    for j in range(len(stack)-1, -1, -1):
        if now > a[stack[j]]:  # 스택의 마지막 원소값을 인덱스로 갖는 수가 현재 값보다 작음 -> 오큰수
            ans[stack[j]] = now  #
            stack.pop()
        else: break
    stack.append(i)  # 현재 인덱스 추가
    i += 1
ans[-1] = -1
for i in ans: print(i, end=" ")

 

 

풀이

- 조건에 따라 입력받은 후 순차적으로 값들을 비교하는 while문을 돌린다. (idx -> 기준)

- 기준값 now를 설정한 후, 스택의 값들을 체크하는데, 스택은 현재값 now까지 오큰수가 지정되지 않은 값들이 저장된 인덱스를 넣은 리스트다.

- 스택의 값들을 체크하면서 now값이 해당 스택에 저장된 인덱스에 위치한 값보다 작은 경우(오큰수가 될 수 없는 경우) break, 큰 경우에는 stack의 값을 pop 하는 방식으로 반복한다.

- 그 다음 출력하면 끝

 

 

알게된 점

- 맨 처음 문제를 보았을 때 완전탐색으로 문제를 해결하는 것은 O(n^2)의 시간복잡도가 나오기 때문에 분명 시간초과가 나올 것이라 생각했다. 

- 그래서 다른 풀이를 생각했고, 중간에 루프를 돌다가 이를 끊을만한 건덕지가 필요했다.

- 고민을 해본결과 인덱스를 저장하는 방식으로 문제를 해결하면 될 것이라고 생각, now 값을 비교하는 for문을 만들었다.

- 그런데 38%쯤에서 시간초과가 발생, 중간에 break문을 넣어주었더니 해결할 수 있었다.

 

 

참고 사이트

-