#3015: 오아시스 재결합

class Freq:
    def __init__(self, value, frequency):
        self.v = value
        self.f = frequency


def main(f=None):


    N = int(input())
    arr = [int(input()) for _ in range(N)]

    stack = []
    cnt = 0

    for i in arr:

        while stack and stack[-1].v < i:
            cnt += stack.pop().f

        if stack:
            last = stack[-1]
            if last.v == i:
                cnt += last.f
                if len(stack) > 1:
                    cnt += 1
                last.f += 1
                continue

            else:
                cnt += 1

        stack.append(Freq(i, 1))

    print(cnt)


if __name__ == "__main__":
    main()

코드 설명

for 루프를 돌면서, 스택에는 내림차순으로 저장한다. 만약 현재 원소가 스택들의 원소들보다 클 경우, 스택들의 원소들을 과감하게 타노스해버린다. 그리고 자기자신을 넣는다.
pop 하면서 자기가 몇개의 원소들을 타노스했는지, 그리고 자기와 같은 값을 가진 놈들의 갯수를 파악해 전부 cnt 에 더한다. 혹시 스택에 자기보다 큰 놈이 있다면 cnt += 1 잊지 않는다.

value, frequency 패어로 저장하는 이유:

그러지 않으면 아래와 같은 테스트 케이스에서 N^2의 시간복잡도가 발생한다.

9 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 … 10만개 … 8 8 8 8 8 8 8 8 …

리스트 안 쓰고 굳이 클래스 쓴 이유

첨에는 리스트 썼는데 가독성이 영 별로여서…

주의할 점

5 4 3 2 2 1 2
2 2 2 2 1 2
1 2 3 4 5
등의 여러 케이스들을 테스팅하면서 반례를 생각하고
cnt += 1 등을 빼먹으면 쉽게 ‘맞왜틀’ 당할 수 있는 까다로운 문제이다.

브레인스토밍

올만에 휴가나와서 저도 한번 백준 일기 해봤읍니다.

모두들 화이팅!

1 Like

이런 일기 형식도 좋네요 ㅇㅅㅇ

1 Like