백준 17298 파이썬 (오큰수)

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

문제 자체를 이해하는데에는 어려움이 없었다.

1. 왼쪽에서 큰 수 발견하면 print(item)
2. 큰 수가 없을경우 print(-1)
3. 숫자가 끝에 있을경우 print(-1)

간단하게 이 방식으로 코드를 짜봤다.

💻 Code

import sys
input = sys.stdin.readline

n = int(input())
data = []
data = list(map(int, input().split()))

def NGE(num_list):
    for i in range(len(num_list)):
        for j in range(i+1, len(num_list)):
            if(num_list[i] < num_list[j]):
                print(num_list[j])
                break
            if(j == len(num_list)-1):
                print(-1)
                break
        else: 
            print(-1)

NGE(data)

• 테스트 코드가 잘 나오긴하지만...시간초과
• 근데 다시 보니까 시간초과 나올만하다 생각하고 코드 짜자

---

📌 모범 풀이

import sys

N = int(input())
L = list(map(int,sys.stdin.readline().split()))

stack = []
A = [-1]*N
print(A)

for i in range(N-1,-1,-1):
    
    while stack:
        if stack[-1] > L[i]:
            A[i] = stack[-1]
            break
        else:
            stack.pop()
    stack.append(L[i])    

print(" ".join(map(str,A)))

1.정답으로 사용할 A리스트를 -1로 초기화
2. for 문을 역순으로 돌린다. (range(N-1,-1,-1))
3. 리스트 끝 원소부터 stack에 하나씩 넣고
3. 오른쪽에 있는 수가 더 클 경우 -1의 값을 stack의 값으로 바꾼다
4. 아닐경우 -1을 그대로 두기 위해 stack에서만 pop()