[백준/3015/파이썬] 오아시스 재결합

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

3015번: 오아시스 재결합

Problem

• 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
• 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

조건

• 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. (즉, 5 4 1 이면 1은 5를 볼 수 있지만, 5는 1을 볼 수 없게 되니까, 서로 볼 수 있는 관계여야한다)
• 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
• 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
• 사람들이 서 있는 순서대로 입력이 주어진다.

SOL

완전탐색

이중 반복문을 이용하면, 위의 문제를 쉽게 해결이 가능하다.  하지만 N<=500,000이므로,N^2으로 푼다면 시간초과가 분명히난다.

 

DP 

누적합 문제와 비슷하게 생겨서, table을 하나 만들어서 반복문을 1개만 딱 쓰려고 했음.

하지만, 반복문을 1개를 쓸려면, 현재 까지의 키의 정보를 가지고 있어야하므로, 결국 자료구조를 이용할 수 밖에 없다는걸 알게되었음. 그래서, DP문제라기 보다는, 자료구조를 적절히 이용하는 문제인거 같다.

 

자료구조 (stack)

자료구조를 활용할 때는, 입력/출력 조건을 잘 나눠야하고, 자료를 어떻게 저장할 것인가 생각을 해야한다.

보통, Stack의 TOP이 어떻게 되냐에 따라서, 값을 넣냐/안넣냐를 정한다. 왜냐하면, stack은 TOP만 뚫려있어서, 비교할 수 있는게 TOP 밖에 없다.

• Stack에 필요한 정보: 키(height),볼 수 있는 사람(cnt)
• stack에 입력되는 경우 : stack이 비어있을 때
• stack의 TOP 과 input 값을 어떻게 비교해서 넣을까
  • input 값이 선형적으로 들어오면, Stack의 TOP과 3가지 경우가 있을 수 있다.
  • Stack[TOP] <h , Stack[TOP]==h,Stack[TOP] >h
  • Stack[TOP] <h : stack[TOP]보다 입력되는 값이 큰 경우 , stack의 TOP이 자신보다 클 때 까지 pop을 해준다.왜냐하면, h값 보다 작은 키는 이제 다음 입력부터는 보지 못하기 때문이다. 이걸 수학적으로 표현하면, 결국 stack을 내림차순으로 관리하게 되는거다.(제일 큰게 stack의 제일 밑바닥 , 제일 작은게 stack의 top)
  • Stack[TOP] ==h : 키가 같은 경우, 서로가 서로를 볼 수 있게된다. 그리고, stack이 비어있지 않다면, 앞에 있는 사람은 볼 수 있으므로, +1을 해준다.
  • stack[TOP] >h : 입력 되는 값이 작은 경우,push해주고, 왼쪽 사람만 볼 수 있으므로, 1을 더 해준다.

# 스택,큐 활용
import sys
HEIGHT, CNT= 0, 1
input =sys.stdin.readline

def solve():
    stk=[]
    ans=0
    for h in arr:
        # stack에 현재 사람보다 작은 사람이 있으면, POP하고, answer에 저장된 CNT 추가
        # h값이 입력될 때, top과 h 값만 비교하면 되기 때문에, stack에는 내림차순으로 관리를 할거임. 
        while stk and stk[-1][HEIGHT] <h:
            ans +=stk.pop()[CNT]
        # 스택이 비어있다면, 입력받은 값과 , cnt(1) 추가
        if not stk:
            stk.append((h,1))
            continue
        # h와 stack top이 같다면, stk에서 pop 해주고, 같은 키인 사람들 만큼 
        if stk[-1][HEIGHT] ==h:
            cnt = stk.pop()[CNT]
            ans+=cnt
            # 현재 키보다 큰 사람이 있다면, 같은 키가 입력 될 때마다, 그 사람도 볼 수 있음.
            if stk:
                ans+=1
            # 현재 키인 사람과 같은 사람이 입력되면, cnt만큼 있으므로, cnt+1을 해준다.
            stk.append((h,cnt+1))
        # stack이 비어있지 않고, stack top이 더 큰 경우 , 왼쪽 사람만 나는 볼 수 있음.
        else:
            stk.append((h,1))
            ans+=1
    return ans

N = int(input().rstrip())
arr = [int(input().rstrip()) for _ in range(N)]
print(solve())