모노토닉 스택(monotonic stack)을 이용한 나보다 큰 첫 번째 수 찾기 문제(오큰수,NGE,next greater element)

1. 모노토닉 스택(monotonic stack)

 

스택 내부의 원소들을 항상 오름차순, 혹은 내림차순 상태를 유지하도록 만드는 자료구조

 

나보다 크거나, 작은 숫자가 언제 처음 나오는지를 찾는데 유용하다.

 

알고리즘 문제에서 보통, "배열에서 나보다 크면서 오른쪽에 있는 수 중 첫번째 수는?" 

 

예를 들어, [5,3,1,4,2]가 있다고 하자.

 

각 숫자에 대해서 "오른쪽에 있는 나보다 큰 첫번째 수"들을 모두 O(N)에 찾으라고 한다면?

 

스택 []을 두고, 왼쪽부터 오른쪽 차례대로 순회한다.

 

스택이 비어있으니까 [5]

 

2번째 3이 들어오는데, 스택의 마지막 수 5가 3보다 더 크므로 그대로 입장 [5,3]

 

3번째 1이 들어오는데 스택의 마지막 수 3이 1보다 더 크므로 [5,3,1]

 

4번째 4가 들어오는데 스택의 마지막 수 1이 4보다 더 작으므로, [5,3]

 

여기서 1의 "오른쪽에 있는 나보다 큰 첫번째 수"는 4

 

다시 3이 4보다 더 작으므로, 3의 "오른쪽에 있는 나보다 큰 첫번째 수"는 4

 

5는 4보다 크므로, [5,4]

 

다시 2가 들어오는데 스택의 마지막 수 4가 2보다 더 크므로 [5,4,2]

 

따라서, 각각 [-1,4,4,-1,-1]으로 찾을 수 있다.

 

스택의 top부분보다 작은 숫자가 들어오면 그대로 받아들이고, 큰 숫자가 들어오면 top을 꺼내면서, 

 

top보다 크면서 오른쪽에서 처음 나오는 숫자는 현재 들어오는 숫자

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

반대로 오른쪽에 있는 수 중 나보다 작은 첫번째로 나오는 수는?

 

스택의 top과 들어오는 수를 비교해서, top이 더 크다면 pop하고 더 작으면 append하면 된다.

 

[5,2,7,1,4]를 보면 [] 스택에서 비어있으니까 [5]

 

2가 들어오는데 5는 2보다 크므로 5의 오른쪽에서 더 작은 첫번째 수는 2이고 [2]

 

7이 들어오는데 2는 7보다 더 작으므로 [2,7]

 

1이 들어오는데 7은 1보다 더 크므로 7보다 작으면서 오른쪽에 나오는 첫번째 수는 1

 

다시 2는 1보다 더 크므로 2보다 작으면서 오른쪽에 나오는 첫번째 수는 1

 

스택은 [1]

 

4가 들어오는데 1은 4보다 더 작으므로 [1,4]

 

따라서 [2,1,1,-1,-1]

 

---------------------------------------------------------------------------------------------------------------------------------

 

2. 연습문제

 

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

 

대놓고 주어진 배열에서 각 원소들의 오른쪽에 있는 수 중 더 큰 첫번째 수를 모든 원소들에 대해 각각 찾으라는 문제

 

모노토닉 스택을 이용하면 O(N)에 해결 가능하다

 

스택에 (원소,인덱스)를 넣고, 왼쪽부터 오른쪽으로 배열을 순회해서, 들어올려는 배열의 원소가

 

스택의 top의 원소보다 더 크다면 top의 원소를 pop하고, 

 

그 원소의 오른쪽에 나오는 수 중 첫번째로 나오는 수는 현재 들어올려는 원소다

 

n = int(input())

A = list(map(int,input().split()))

stack = []

answer = [-1]*n

for i in range(n):
    
    while len(stack) > 0 and stack[-1][0] < A[i]:
        
        p,j = stack.pop()
        answer[j] = A[i]
    
    stack.append((A[i],i))

print(*answer)

 

 

스택에 (원소,인덱스)를 넣지 않고 (인덱스)만 넣어도 된다.

 

인덱스만 알면 배열 A에서 어떤 원소인지 아니까

 

n = int(input())

A = list(map(int,input().split()))

stack = []

answer = [-1]*n

for i in range(n):
    
    while len(stack) > 0 and A[stack[-1]] < A[i]:
        
        j = stack.pop()
        answer[j] = A[i]
    
    stack.append(i)

print(*answer)

 

 

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

 

각 원소에서, 오른쪽으로 바라볼때, 볼수 있는 원소의 개수를 찾는 문제

 

현재 원소 A[i]보다 오른쪽에서 처음으로 큰 수 A[j]를 찾아서 i+1~j-1까지 개수를 전부 세서 더하면 된다.

 

결국 모노토닉 스택을 이용해서 오큰수의 위치를 찾기만 하면 구할 수 있는 문제

 

위에서는 왼쪽에서 오른쪽 정방향으로 순회하고 있지만

 

다음과 같이 오른쪽에서 왼쪽으로 역방향 순회를 할 수도 있다

 

이러면 stack에는 현재 수 A[i]의 오른쪽에 있는 수들이 top에서 순서대로 있음

 

현재 수 A[i]와 stack의 top을 비교해서 A[i]가 더 크다면 오른쪽에 있는 수중 더 작은 수들을 만났으니 pop해버리고

 

A[i]가 더 작다면 드디어 오른쪽에 있는 수 중 나보다 더 큰 수를 처음 만났으니 반복문을 탈출

 

그러면 현재 i번째 인덱스에서 오른쪽에 있는 수 중 나보다 더 큰 수는 stack의 top

 

이렇게 하면 while문 밖에서 기록을 해야하는 차이가 있긴해

 

from sys import stdin

n = int(stdin.readline())

A = []

for _ in range(n):
    
    h = int(stdin.readline())
    A.append(h)

B = [-1]*n

stack = []

for i in range(n-1,-1,-1):
    
    while len(stack) > 0 and stack[-1][0] < A[i]:
        
        stack.pop()
    
    if len(stack) > 0:
        
        B[i] = stack[-1][1]

    stack.append((A[i],i))

count = 0

for i in range(n-1):
    
    if B[i] == -1:
        
        count += n-1-i
    
    else:
        
        count += B[i]-1-i

print(count)

 

 

정방향 역방향 순회할때 또 생각해야할 점은 들어올려는 수와 stack의 top이 서로 같을수도 있는데

 

문제 조건상 같은 빌딩이 있더라도 그 이후는 못보기 때문에

 

찾아야하는 수는 오른쪽에서 나와 같거나 큰 수중 첫번째로 나오는 수

 

정방향으로 순회하면 stack의 top을 기준으로 i번째 원소와 비교했을때 크거나 같은 수를 찾아야하므로,

 

stack[-1][0] <= A[i]여야겠지만,

 

역방향으로 순회하면 i번째 원소를 기준으로 stack의 top들을 보면서 처음으로 크거나 같은 수를 찾아야하므로,

 

i번째 원소보다 작은 얘들은 다 빼버려야함

 

그래서 stack[-1][0] < A[i]

 

외울게 아니라 논리적으로 생각해야함

 

from sys import stdin

n = int(stdin.readline())

A = []

for _ in range(n):
    
    h = int(stdin.readline())
    A.append(h)

B = [-1]*n

stack = []

for i in range(n):
    
    while len(stack) > 0 and stack[-1][0] <= A[i]:
        
        p,j = stack.pop()
        B[j] = i
    
    stack.append((A[i],i))

count = 0

for i in range(n-1):
    
    if B[i] == -1:
        
        count += n-1-i
    
    else:
        
        count += B[i]-1-i

print(count)