[백준] 31858. 간단한 순열 문제

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

문제 요약

• 순열 P가 주어짐
• 조건을 만족하는 (i,j) 쌍의 개수 찾기 (문제 수식 참고)
• 최소값(제일 왼쪽, 제일 오른쪽) > 최대값(그 사이 값들, 0)

접근법

• 모든 경우의 수를 찾기에는 N^2의 시간이 발생
• 처음에는 바로 문제 이해가 안됨. 예제의 수열에 대해서 만족하는 경우를 찾아봄
• ${P_i}$ 가 최소값이 되는 경우는 언제일까?
  • 예제에서 주어진 4,2,3,1,5에서 3이 최소값이 되는 순간은
  • 4,2,3
  • 3,1,5
• ${P_i}$가 왼쪽에 있는 경우를 먼저 생각해보면
• 오른쪽에 수 많은 숫자중에 최초로 ${P_i}$ 보다 큰 숫자가 나타나는 경우가 있을 것임 : ${P_j}$로 표현
• 일단 ${min(P_i,P_j)=P_i}$ 는 만족
• ${max(P_{i+1}, ... P_{j-1})}$ 은 ${P_i}$ 보다 작음. 왜냐면 최초로 큰 숫자가 ${P_j}$이므로
• 만족하는 경우를 하나 찾았다!!
• ${P_j}$의 왼쪽에 있는 것들은 ${P_i}$가 최소값이 아니므로 경우에서 제외(그 땐 다른 숫자가 최소값이 될 것이고 그때 다룰게 됨)
• ${P_j}$의 오른쪽에 있는 것들은 ${P_i}$가 최소값이 된다고 해도 이미 중간에 ${P_j}$가 있어서 실패
• 따라서 어떤 숫자 ${P_i}$에 대해서 오른쪽에서 최초로 이 숫자보다 큰 값이 나타나는 경우를 찾으면 됨
• 왼쪽도 마찬가지 논리
• 구간트리를 써야하나.... 생각하다가
• 그런데 조금 더 확장해서 생각해보면 왼쪽(또는 오른쪽)에 이 숫자보다 큰 숫자가 있는지만 판단하면 됨
  • 스택 사용
  • 지금 다루는 숫자보다 큰 값이 나타날때까지 모두 pop 하고 push