백준 #31858 간단한 수열 문제

문제 링크

[31858 간단한 수열 문제]

문제 설명

1부터 N 사이의 숫자로 이루어진 배열이 주어진다. 이때 숫자의 순서는 랜덤 두 숫자를 골랐을 때 두 숫자의 최소 값이 두 숫자 사이의 최대값보다 큰 경우의 수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
arr = list(map(int, input().split()))
stack = []
cnt = 0
for i in range(N - 1, -1, -1):
    if i == N - 1:
        stack.append(arr[i])
    else:
        cur = arr[i]
        while stack and stack[-1] < cur:
            stack.pop()
            if stack:
                cnt += 1
        stack.append(cur)
        cnt += 1

print(cnt)

풀이

가장 맨 뒤에 숫자부터 스택에 넣어주면서 스택의 top에서 bottom방향 기준으로 오름차순을 유지시켜주었다. 오름차순을 유지시켜주는 과정에서 중간에 빼낼 원소가 있다면 현재 들어갈 원소와 그 원소의 쌍도 조건을 만족하기 때문에 개수를 더해주었다. 단, pop을 했는데 스택이 비어있다면 더해주지 않는다. 왜냐하면 while문을 빠져나와서 현재 원소를 넣는 과정에서 개수를 자동을 세어주기 때문에 중복으로 세어지기 때문!!