[Python/백준] 3015 오아시스 재결합

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

3015번: 오아시스 재결합

<문제 해설>

stack 문제이다. 사람들은 왼쪽에 보는 사람만봐서 중복을 없에고 왼쪽 사람들을 stack으로 관리한다.

시간복잡도를 줄이는 것이 중요한테 왼쪽 사람들의 키가 겹칠경우 배열 한칸을 차지하지 않고 같은 키의 사람의 수가 몇인지 기록해야 한다.

[9,3]

이렇게 stack에 저장된다(stack은 2차원 배열) index 0은 사람의 키 index 1은 몇명이 이키인지 나타내는 것이다.

1. stack이랑 출력할 값을 저장할 변수인 output을 정의해준다.
2. 이제 값들을 받고 바로바로 처리한다.
3. 현제 받은 값이 1명있다고 count변수도 정의해준다.
4. 만약 stack의 마지막 값이 현재 받은 값보다 작다면 이제 가려질 사람이니 stack에서 뺴고 output에 pop된 값의 1번재 index(사람의 수) 를더해준다. 2번으로 돌아간다.
5. 만약 stack의 마지막 값이 현재 값이랑 같다면 count를 마지막 값의 사람 수만큼 더해주고 output에도 더해준다.
   그리고 stack에서 뺸다. 2번으로 돌아간다.
6. 만약 마지막 값이 현재값보다 큰경우 output에 1추가하고(키큰사람은 1명밖에 못추가한다.) 중지한다.
7. stack에 [현제키,count]를 추가해준다.
8. 마지막으로 output을 출력하면 된다.

<예시>

위 그림의 첫줄은 입력되는 수이다.

둘째 줄은 볼수 있는 수가 어떤수인지 보여주고

셋째 줄은 output의 값이 변하는 걸 보여준다.

마지막은 stack에 존재하는 수이다.

<코드>

import sys

N = int(sys.stdin.readline())
stack = []
output = 0
for _ in range(N):
    now = int(sys.stdin.readline())
    count = 1
    while(stack):
        if stack[-1][0] < now:
            output += stack[-1][1]
            stack.pop()
        elif stack[-1][0] == now:
            output += stack[-1][1]
            count += stack[-1][1]
            stack.pop()
        else:
            output += 1
            break
    stack.append([now,count])

print(output)

<고찰>

처음으로 풀어본 플레티넘 문제이다. 확실히 플레티넘 문제부터는 단순 구현,자료구조,알고리즘 뿐만 아니라 시간이 최대한 들지 않도록하는 최적화가 가장 중요한거 같다. 키가 같은 사람을 처리하는 로직을 구현하지 않아서 에러가 났었다.