[백준] 17298번 오큰수 - 파이썬(Python)

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

17298번: 오큰수

 

문제

 

21.04.11 접근법

1. 차례대로 2개 비교
2. 오른쪽이 작으면 위치 스택에 저장
3. 오른쪽이 크면 오른쪽 값을 왼쪽 인덱스를 스택에 저장
4. 스택이 빌 때까지 반복

21.04.11 코드

n=int(input())
arr=list(map(int,input().split()))
ans=[-1]*n
stack=[0]
i=1

while stack and i<n:
    while stack and arr[stack[-1]]<arr[i]:
        ans[stack[-1]]=arr[i]
        stack.pop()
    stack.append(i)
    i+=1

for i in ans:
    print(i,end=' ')

 

21.07.28 접근법

 

 

예전에 이 문제를 풀었을 땐 풀이를 봐도 이해가 안가서 2월엔 포기했다가 4월엔 대충 이해하고 넘겼었다.

이번에 다시 봐도 멘붕이 왔지만, 이번에는 제대로 이 어려움을 극복해보고자 결심했고 답을 보지 않고 해결하기로 결정했다.

 

처음 직면했던 문제는 다음과 같다.

수열 앞에서부터 순차적으로 살펴보려 하는데, 찾은 것과 아직 못 찾은 것의 구분을 어떻게 할까?

=> 자신보다 큰 값을 찾지 못한 아이는 스택에 넣어두자.

 

그리고 그것을 해결하니, 다음엔 아래와 같은 문제를 직면했다. (이 부분의 답을 생각하기 위해 거의 하루를 보냈다...)

값을 찾아 pop을 했을 때, pop한 수열 값에 어떻게 답을 집어넣을 것인가?

... 해당 값에 대한 걸 하나하나 찾아넣으면 많은 for문을 돌려야 하기에 시간 잡아먹음. (비효율적)

=> pop하는 값이 인덱스이면 됨! 스택에 애초부터 인덱스를 넣으면 인덱스로 한 번에 찾아갈 수 있음!

 

예전에 시간의 효율성을 위해 스택의 값을 인덱스로 활용했던 것을 기억해냈다. 이에, 그를 적용해봤고 정말 감격스럽게 한 번에 통과할 수 있었다.

 

 

[주요 변수]

arr : 입력받은 수열의 배열

comp : 오큰수를 찾지 못한 수열 값의 인덱스를 저장하는 배열

ans : 찾은 오큰수를 보관하는 배열

 

[과정]

1. arr 앞에서부터 인덱스로 탐색

2. comp 안에 있는 값과 현재 인덱스 위치의 값을 비교

3. 현재 인덱스의 값이 크면 ans의 해당 인덱스 위치에 오큰수 저장

4. 현재 인덱스도 오큰수를 찾기 위해 comp에 append

 

21.07.28 코드

N=int(input())
arr=list(map(int,input().split()))
ans=[-1 for i in range(N)]
comp=[]

for i in range(N):
    while comp and arr[comp[-1]]<arr[i]:
        ans[comp.pop()]=arr[i]

    comp.append(i)

for i in ans:
    print(i,end=' ')