문제
https://www.acmicpc.net/problem/17298
코드
처음 작성한 코드는 다음과 같다. 시간 복잡도를 고려하지 않고, 올바른 출력만 고려해서 작성했기에 시간 초과가 떴다.
import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().rstrip().split(" ")))
for i in range(len(seq)):
temp = [x for x in seq[i + 1:] if x > seq[i]]
if temp:
print(temp[0], end = " ")
else:
print(-1, end = " ")정답 코드는 아래와 같다.
import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split(" ")))
NGE = [-1] * N
stack = []
for i in range(N):
while stack and (seq[stack[-1]] < seq[i]):
NGE[stack.pop()] = seq[i]
stack.append(i)
print(*NGE)처음 제출했던 코드는 list comprehension을 생각하면, 결국 2중 for문이라 O(N^2)의 시간 복잡도를 갖는다. 그래서 정답 코드는 stack을 사용해 시간 복잡도를 O(N)에 가깝게 만들었다고 할 수 있다.
NEG는 정답이 저장된다. 즉, -1로 초기화된 상태에서 seq의 해당 인덱스보다 큰 값이 등장하면 그때 NEG의 값이 바뀌고 이러한 값이 없다면 -1로 유지된다.
stack은 자신보다 큰 값이 존재하지 않아 우선 보류해둔 인덱스 값이 저장된 리스트이다.
주어진 수열을 순차적으로 탐색한다.
만약 stack이 비어있지 않고, 현재 seq[i]의 값이 stack에 저장된 인덱스에 대응하는 seq의 값보다 크다면 seq[i]가 그 수의 오큰수가 된다. (가장 왼쪽에 있는 현재 값보다 큰 수)
이런 식으로 seq의 끝까지 탐색한 뒤, NEG를 출력하면 정답이다.
기타
첫 골드 문제였다.
문자 뒤에 white space가 붙어 있더라도 int로 형 변환하면 white space는 무시되는 것 같다.
예를 들어, x = '5\n'일 때, int(x) = 5가 된다.
파이썬에서 배열을 출력할 때, 배열명 앞에 *를 붙이면 공백을 기준으로 원소들만 출력된다.
참고한 사이트는 다음과 같다.
https://hooongs.tistory.com/329
