[백준] 17298번 (python 파이선)

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

17298번: 오큰수

 

import sys

_ = input() # 사용하지 않는다
arr = list(map(int,sys.stdin.readline().strip().split()))
stack = []
result = [-1] * len(arr)

for i in range(len(arr)-1):
  stack.append(i)
  while stack and arr[stack[-1]] < arr[i+1]:
    result[stack.pop()] = arr[i+1]
print(*result)

 

처음에 생각없이 문제에 나온대로 풀다보면 시간초과를 겪는다.

하긴.. 수열의 크기가 최대 백만개인데... N제곱 으로 풀면 무조건 시간초과지.

 

내 머리론 하루이틀로는 해결 불가능이라 판단하고 구글링했다.

대다수 사람들이 스택으로 이 문제를 풀었다.

코드를 봐도 이해가 되지 않았다. 단, 3~4줄짜린데...

디버깅표 따라서 계산하면 이해는 되지 않았지만 답은 나왔다.

 

그러다 저녁밥 먹으러 가는 길에 깨달음을 얻었다.

스택의 핵심은 후입선출 + 그리고 쌓고(push) 빼는 것(pop)이다.

쌓고 빼는 것은 2가지의 행동이며 이는 켜고 끄다, 열고 닫다 와 같은 2진법 개념에 적용시킬 수 있다.

즉, 후입선출 + 2진 개념을 가진 문제에 적용할 수 있다.

 

예를들어 "<"와 ">"로 이루어지고 그 수가 짝이 맞는 문장 "< < > >" 은 다음과 같이 나타낼 수 있다.

(스택에 넣는 데이터는 "ㅁ"로 표시했다)

1. "<" => [ㅁ]
2. "<<" => [ㅁ, ㅁ]
3. "<<>" => [ㅁ]    (pop: ㅁ)
4. "<<>>" => [ ]    (pop: ㅁ)

2진 개념 : "<"와 ">"로 2진 개념이 나타내어진다.

후입 선출 : "<"가 나올때마다 ㅁ가 쌓이고 ">"가 나타날때 마지막으로 push된 "ㅁ"가 먼저 pop된다.

 

이 개념을 고려했을때 위의 문제는 다음과 같이 변경될 수 있다.

 

스택에 쌓이는 데이터 : 수열의 인덱스( 0부터 N까지. )

2진 개념 : 스택 최상단 인덱스에 해당하는 수열의 수 보다 다음 수가 작거나 같다 => push

              스택 최상단 인덱스에 해당하는 수열의 수 보다 다음 수가 크다 => pop

후입 선출 : 가장 마지막에 push된 인덱스부터 가장 먼저 push된 인덱스 순으로 평가한다.

 

예를 들어 arr = [ 3, 2, 1, 5, 4 ] 이라는 수열이 있다 하자.

오큰수로 된 수열은 arr와 같은 크기의 -1요소로 구성한다. result = [ -1, -1, -1, -1, -1 ]

1. 비교를 하기위해선 스택이 비워져 있으면 안된다. 시작 인덱스인 0을 push 한다. 현재 스택 [ 0 ]
2. 스택의 최상단인 0을 인덱스로 갖는 3과(=첫 번째 자리수) 그 다음수인 2를 비교한다.
3. 만약 다음수인 2가 더 큰 수였다면 pop을 해서 스택을 비우겠지만, 그렇지 않으므로 2의 인덱스를 push 한다. 현재 스택 [ 0, 1 ]
4. 스택의 최상단인 1을 인덱스로 갖는 2와(=두 번째 자리수) 그 다음 수인 1을 비교한다.
5. 만약 다음수인 1이 더 큰 수 였다면 pop을 해서 스택을 비우겠지만, 그렇지 않으므로 1의 인덱스를 push 한다. 현재 스택 [ 0, 1, 2 ]
6. 스택의 최상단인 2를 인덱스로 갖는 1과(세 번째 자리수) 그 다음 수인 5를 비교한다.
7. 5가 1보다 크므로 스택에서 pop을 한다. 그리고 5를 result의 인덱스 2(세 번째 자리수)에 넣는다. 현재 스택 [ 0, 1 ] 
8. 다음 수로 가기전에 남아있는 스택을 처리한다.
9. 스택의 최상단인 1을 인덱스로 갖는 2와(=두 번째 자리수) 방금 비교한 5를 비교한다.
10. 5가 2보다 크므로 스택에서 pop을 한다. 그리고 5를 result의 인덱스 1(두 번째 자리수)에 넣는다. 현재 스택 [ 0 ]
11. 스택의 최상단인 0을 인덱스로 갖는 3과(=첫 번째 자리수) 방금 비교한 5를 비교한다.
12. 5가 3보다 크므로 스택에서 pop을 한다. 그리고 5를 result의 인덱스 0(첫 번째 자리수)에 넣는다. 현재 스택 [ ]
13. 3, 2, 1일때 쌓은 스택을 5에서 모두 제거 했다. 마치 "<<<>>>"와 같다.
14. 5의 인덱스를 push한다. 현재 스택 [ 3 ]
15. 스택의 최상단인 3을 인덱스로 갖는 5와(=네 번째 자리수) 그 다음 수인 4를 비교한다.
16. 만약 다음 수인 4가 더 큰 수 였다면 pop을 해서 스택을 비우겠지만, 그렇지 않으므로 4의 인덱스를 push한다. 현재 스택 [ 3, 4 ]
17. 반복이 끝났다. 남겨진 스택은 [ 3, 4 ] 이다. 즉, 5와 4의 오름수는 찾지 못하여서 스택에서 pop되지 못한 것이다. 따라서 result의 3, 4번 인덱스는 그대로 -1을 유지한다.
18. 최종 결과로 result = [ 5, 5, 5, -1, -1 ]이 된다.