문제 확인
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
나의 풀이
- 완전 탐색으로 접근할 경우 $O(N^2)$ 이고, numbers의 길이는 최대 100만이기 때문에 시간 초과가 발생한다.
- 뒷 큰수는 앞에서 부터 값을 보관해 뒀다가, 더 큰 값이 나오면 제거하고, answer 정보를 업데이트하는 방식으로도 얻을 수 있다.
- 이 경우 스택에 값 numbers의 idx를 저장해두고, numbers의 숫자가 가장 최근에 입력된 값과 유사한 지 비교하면 된다.
# 자신보다 뒤 + 크면서 가장 가까이 있는 수 : 뒷 큰수
# 뒷 큰수가 없으면 -1
# 완전 탐색 불가
# 큰 수가 없으면, 큰 수가 나올 때 까지 보관하고 확인해야 함
# 그러다가 큰 수가 나오면 바로 제거
# 스택을 활용해서 풀 수 있음
def solution(numbers):
# 정답 정보
answer = [-1] * len(numbers)
# 스택
stack = []
for idx, num in enumerate(numbers):
# 큰 수가 나온 경우, 그 수를 사용해 정답 정보 갱신
while stack and numbers[stack[-1]] < num:
answer[stack.pop()] = num
stack.append(idx)
return answer