백준 17298 오큰수 파이썬 풀이

난이도 : 골드4

풀이일 : 03131

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

17298번: 오큰수

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답

import sys

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))

stack = [arr[-1]]
num = [-1] * n
for i in range(n-2, -1, -1):
    while stack:
        if stack[-1] > arr[i]:
            num[i] = stack[-1]
            break
        else:
            stack.pop()
    stack.append(arr[i])

print(num)

코드 구성

• 스택의 마지막 요소부터 한칸씩 왼쪽으로 순회
• 오큰수가 없다면 -1 출력 -> 배열 길이만큼 -1을 넣은 배열 생성
• 스택의 요소가 오큰수에 해당하는지 확인
  • 해당한다면, num 배열에 기록
• 순회 중 더 큰 값을 만나면 스택 요소 교체

 

틀린 이유

• 출력 형식

---

최종 정답

import sys

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))

stack = [arr[-1]]
num = [-1] * n
for i in range(n-2, -1, -1):
    while stack:
        if stack[-1] > arr[i]:
            num[i] = stack[-1]
            break
        else:
            stack.pop()
    stack.append(arr[i])

print(*num)

코드 변화

• 마지막 프린트문 * 추가

---

느낀점

오늘은 알고리즘 문제를 풀지 못해 이전에 풀어둔 것들 중 적당한 것을 골라왔다.

쉬운 문제를 풀더라도 꾸준히 풀자ㅠㅠ