오아시스 재결합 (3015번) - 백준 (BOJ)

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

3015번: 오아시스 재결합

 

 

백준 - 오아시스 재결 (PATRIK) (3015번)

 

난이도 : Platinum 5

알고리즘&자료구조 : Stack (스택)

 

---

 

스택을 활용해서 풀 수 있는 문제이다.

 

Stack으로 오름차순의 순열을 유지하며 해결할 수 있는

전형적인 스택 문제였다.

 

 

 

< 전체 코드 >

import sys
input = sys.stdin.readline


class Waitings():
    def __init__(self, N):
        pairs = 0
        stack = []
        for _ in range(N):
            x = int(input())
            while stack and stack[-1][0] < x:
                _, acc = stack.pop()
                pairs += acc
            if stack and stack[-1][0] == x:
                pairs += stack[-1][1]
                stack[-1][1] += 1
                if len(stack) > 1:
                    pairs += 1
            else:
                if stack:
                    pairs += 1
                stack.append([x, 1])
        self.answer = pairs
        
        
if __name__ == '__main__':
    wating_line = Waitings(int(input()))
    print(wating_line.answer)

 

 

 

---

 

① 스택으로 활용할 리스트 stack을 생성한다.

서로 볼 수 있는 쌍의 개수를 셀 pairs를 0으로 초기화한다.

 

 

 

② 각 사람의 높이 x를 입력받는다.

 

x가 stack의 마지막 원소보다 작을 때까지,

 while stack and stack[-1][0] < x

 

stack의 마지막 원소를 계속 제거한다.

_, acc = stack.pop()

 

그 과정에서 제거하는 높이의 사람 수를 pairs에 더한다.

pairs += acc

 

 

 

③ 만약 x와 같은 높이의 사람들이 stack에 존재한다면,

pairs에 그 사람들의 수를 더해주고,

stack에 남아있는 해당 높이의 사람 수에 1을 더해준다.

 

만약 x보다 큰 높이의 사람들이 stack에 남아있다면,

pairs에 1을 추가로 더해준다.

 

if stack and stack[-1][0] == x:
    pairs += stack[-1][1]
    stack[-1][1] += 1
    if len(stack) > 1:
        pairs += 1

 

 

 

④ x와 높이가 같은 사람이 stack에 없으면서

stack에 x보다 높이가 높은 사람이 남아있다면,

pairs에 1을 추가로 더해준다.

 

이후 stack에 [현재 사람 높이 x, 사람 수 1] = [x, 1] 을 추가해준다.

 

else:    
    if stack:
        pairs += 1
    stack.append([x, 1])

 

 

 

⑤ 마지막으로 pairs를 출력하면 된다.