[HackerRank][Python3] Maximum Element

Problem :

https://www.hackerrank.com/challenges/maximum-element/problem

My Solution :

#!/usr/bin/env python3


class Stack(object):
    def __init__(self, data=1):
        self.data = data
        self.prev = None
        self.next = None
        self.maximum = data


tail = Stack()

N = int(input())
for _ in range(N):
    line = input()
    if 1 < len(line):
        t, x = map(int, line.split())
        node = Stack(x)
        node.prev = tail
        tail.next = node
        node.maximum = max(node.maximum, tail.maximum)
        tail = node
    else:
        if not tail.prev:
            raise Exception('Stack is empty!')
        elif line == '2':
            tail = tail.prev
            tail.next = None
        else:
            print(tail.maximum)

Comment :

Stack 구조이기 때문에 LIFO (후입선출) 이다. 따라서 아래쪽에 있는 node는 최대값을 구함에 있어 자기보다 위쪽에 있는 node의 값을 알 필요가 없다. 아래쪽에 있는 node는 바닥부터 자기까지의 최대값만 기억하고 있으면 된다. 새로 삽입되는 node는 바로 직전 node에 기록되어 있는 최대값과 자신의 data만 비교하면 된다.

My Solution2 :

이번에는 원래 Stack과 최대값 추적용 Stack을 활용한 버전이다.

#!/usr/bin/env python3

stack = []
max_stack = []

N = int(input())
for _ in range(N):
    line = input()
    if 1 < len(line):
        t, x = map(int, line.split())
        stack.append(x)
        if not max_stack:
            max_stack.append(x)
        else:
            max_stack.append(max(x, max_stack[-1]))
    elif line == '2':
        stack.pop()
        max_stack.pop()
    else:
        print(max_stack[-1])