[BOJ] 백준 17298번 오큰수 파이썬

문제 > 백준 17289번 : 오큰수

---

출처 : 백준 17298번 오큰수

17298번: 오큰수

---

▶ 나의 풀이 in Python3

N = int(input())
numbers = list(map(int, input().split()))

stack = [];answer =[-1] * N

# solution
for i in range(N):
    while stack and numbers[stack[-1]] < numbers[i]:
        answer[stack.pop()] = numbers[i]
    stack.append(i)

print(*answer)

 

▶ 알고리즘 풀이 (스택)

1. 단순히 오른쪽에 있는 가장 큰 값이 아니라 해당 수열 오른쪽에 있으면 더 큰 수들 중 가장 왼쪽에 있는 값을 요구하므로 스택 활용 결정
2. 총 N개의 값을 가진 answer을 완성해야 하므로 N번 for문 형성
3. stack의 LIFO 성질 (마지막에 넣은게 가장 먼저 나옴) 활용하여 조건에 맞지 않을 경우, answer 값은 -1 조건에 맞는다면, answer에 오큰수 대입
4. for문 자체를 index로 잡았기에 스택은 index로 활용

문제 자체는 쉽지만, 풀기에는 조금 난이도 있는 문제였습니다.

저도 처음엔 쉽게 접근했지만, 난해하여서 충분한 시간을 고민하고 다른 분들이 어떻게 효율적으로 풀었는지 참고하여서 풀었습니다. 마지막에 print할 때, 공백 기준으로 리스트 원소들을 출력하기 위해 answer 리스트에 *를 붙였습니다.