백준 오큰수 파이썬

문제링크

17298번: 오큰수

언뜻보면 굉장히 간단한문제 하지만 정답률이 낮았고

그말은 시간초과 문제가 있을확률이 매우 높다

채점 현황을 가보니 역시나 시간 초과가 많았다

 

시간초과가 날것같지만 그냥 직관적으로 머리에 바로 떠오르는 방법으로 구현해보았다

왼쪽에서 오른쪽으로 나보다 큰수인지를 탐색하다가 발견시 출력하는 그런 방식이다

끝까지 탐색했는데 나보다 큰수가 없거나 그냥 내 오른쪽에 수가 없는경우 -1을 출력한다

 

N=int(input())
ans=[]
a=list(map(int,input().split()))
for i in range(N):
    error=0
    for j in range(i+1,N):
        if a[i]<a[j]:
            ans.append(a[j])
            error+=1
            break
            
    if error == 0:
        ans.append(-1)
    
for i in ans:
    print(i, end=' ')

역시 시간초과가 났다

 

아무리 짱구를 굴려도 마땅한 해결책이 떠오르지않는다 답을 봐야할것같다 궁금하기도하고

 

정답풀이

[백준17298번] 오큰수 / Python3

원래는 하나 하나씩 오큰수를 찾는 느낌이었다면 

이방법은 약간 숫자들이 스택이라는 자료구조 이름이라는 버스를 타고다니면서 원하는 오큰수 정류장에 내리는 느낌이다

버스는 수열의 모든수를 한번 훑고 끝이난다 

 

대강 이해는 한것같으니 한번 구현해보자

1. 수열의 수를 하나씩 stack에 담는다

2. stack에서 가장 최근에 들어온수보다 작은 수들은 모두 pop 되며 

    가장 최근에 들어온수를 오큰수로 갖게 된다

3. stack에서 빠져나오지못한 수들은 -1을 오큰수로 갖게 된다

 

구현

N=int(input())
sl=list(map(int,input().split()))
stack=[[9000000,9000000]]
ans=[-1]*N
for i in range(N):
    while stack[-1][1] < sl[i]: # 현재수보다 stack의 숫자가 더 작을때
        ans[stack[-1][0]]=sl[i] # 현재값으로 오큰수를 가진다
        stack.pop() # 오큰수를 배정받은 숫자는 stack에서 pop 해준다
    
    stack.append([i, sl[i]]) # A(i) stack에 담기(인덱스, 숫자)

print(*ans) # 정답 출력

문제가 꽤나 어렵다고 느껴졌었다

스택 문제를 더 풀어보고싶은데 단계별에선 4문제밖에 있지않아서 아쉬웠다 다음에 더 풀어보고싶다는 생각이 들었다