서론
백준 문제를 풀기 시작하면서 처음으로 접한 골드 문제다.
처음 문제를 읽곤 이게 왜 골드?라고 생각하며
막힘없이 코드를 작성했지만 시간초과 나서 멘붕 😱
풀이의 접근법을 생각해내는데 꽤 오랜 시간이 걸린 것 같다...
처음 풀이 (시간 초과)
N = int(input())
seq = list(map(int, input().split()))
for i in range(N):
hasNGE = False
for j in range(i, N):
if seq[i] < seq[j]:
print(seq[j], end=' ')
hasNGE = True
break
if not hasNGE:
print('-1', end=' ')사고의 과정 💭
처음은 이중 for문을 사용하여 풀었다.
입력받은 수열을 일단 리스트의 형태로 저장하였다.
그 다음 리스트를 순회하며 해당 원소 i와
i의 오른쪽에 나오는 모든 원소 j들과 크기를 비교해나가며
i < j일 경우 j를 출력하도록 하였다.
이때 i의 오른쪽에 나오는 모든 j들이 i보다 작거나 같다면 -1을 출력하도록 하였다.
-1의 출력 여부는 변수 hasNGE에 저장하였다.
하지만 이중 for문을 사용하면 시간복잡도가 O(N^2)가 된다.
바깥쪽 반복문이 N번 반복하고 안쪽 반복문이 N-(현재 인덱스)만큼 반복하기 때문이다.
따라서 시간 초과가 발생하여 문제를 해결할 수 없었다.
스택을 사용한 문제 접근 💡
그렇다면 어떻게 해결해야 할까?
우선 for문을 통해 리스트를 순회하며 해당 원소를 스택에 삽입한다.
스택은 오큰수를 찾지 못한 원소들을 모아놓는 역할을 한다.
오큰수를 찾았다면 스택에서 꺼낸다(pop).
정리하면 for문에서 한번 반복이 실행될 때 하는 일은 크게 2가지이다.
1️⃣ 리스트의 현재 원소와 스택의 상단에 있는 원소의 크기를 비교한다.
이때 리스트의 원소가 더 크다면 stack[-1]의 오큰수를 찾은 것이다.
따라서 스택의 상단에 있는 원소를 꺼낸다(pop).
만약 스택의 상단에 있는 원소가 더 크거나 같다면 어떤 일도 하지 않고 2️⃣로 넘어간다.
2️⃣ 리스트의 현재 원소를 스택에 삽입(append)한다.
아래의 그림을 통해 이해를 돕도록 하겠다.
정답 코드
N = int(input())
lst = list(map(int, input().split()))
stack = []
result = [-1] * N # 오큰수를 담을 리스트
for i in range(N):
# 1️⃣
while stack and lst[i] > lst[stack[-1]]:
result[stack.pop()] = lst[i]
# 2️⃣
stack.append(i)
print(*result)잘못된 정보, 오탈자를 발견하면 편하게 댓글로 말씀해주세요!
질문 또한 환영합니다 🤗
