Stack 만들기 (Class에 관하여)

10828번: 스택 (acmicpc.net)

10828번: 스택

 

백준 문제이지만, 이번 시간에는 python에서 class를 지정하고, method 등을 만들어보는 시간이 될 것이므로 python 카데고리에 이 글을 포스팅하겠다.

 

우선, Class 란 무엇인가? 

Class는 일종의 템플릿 혹은 틀(Frame)이라고 보면된다.

어떤 함수가 서로 다른 상황에서 반복적으로 쓰여진다고 가정할 때, 그것을 하나하나 만드는 것은 굉장히 비효울적인 일이 될 것이다. 

또한, 그 함수들을 일괄적으로 수정할려고 할 때도, 하나하나 수정해줘야하므로 여간 귀찮은 일이 아닐 수가 없다.

 

그런 당신을 위해서 존재하는 것이 Class 이다.

 

그러면 이번 시간에는 Stack형 자료구조를 만들어보면서 Class 에 대해 공부를 해보겠다. 

 

우선 모든 존재에는 이름이 있듯이, Class에도 이름이 존재해야한다. 

아주 창의적이고 유머러스한 이름을 지을 수 있겠지만, 이번시간은 기초 내용을 학습할 것이므로 그러지 아니하겠다.

아주 재미없게 Class 명을 MyStack으로 지정하자. 

class MyStack:

모든 프로그램이 시작할 때, 초기화(Initializing)을 하듯이, Class에도 초기화가 필요하다. 

그 초기화를 담당하는 Method가 아래와 같은 __init__(self) Method이다. 

    def __init__(self):
        self.stack = [None] * 10001
        self.idx = 0

이런 __(Method Name)__ 가 붙은 Method는 Magic method 혹은 Special Method라 하여, 파이썬의 내장함수를 현재 Class 안에서도 사용할 수 있게 불러오는 것이다. 

 

__init__(self) 는 보이다시피 초기화를 담당하고 있고, 초기화의 대상자는 self이다. 

이 Method를 통해 이 Class 안에서의 self는 어떠한 속성도 붙어있지 않고, 순수한 Instance가 되었으며, 이제부터 우리의 입맛에 맞게 커스터마이징해주면 된다. 

 

이제 이 MyStack이라는 Class를 지정해주었을 때, stack은 빈 리스트가 되고, 이 때의 idx(스택의 길이, 혹은 위치)는 0이 된다. 

어떤식으로 채워줄 지, 안에 있는 Value들을 어떤식을 다룰지, 다음 단계로 나아가보자. 

 

우선, 백준 문제에서는 어떠한 기능을 원하고 있을까? 

 

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

push는 다음과 같이 구성한다.

    def push(self, num):
        self.stack[self.idx] = num
        self.idx += 1

push Method에서 num(입력 조건에 의해 정수값이 주어진다.)을 stack에 추가하고, idx를 추가한다. 

 

 

pop은 다음과 같이 구성한다.

    def pop(self):
        if self.idx <= 0:
            return -1
        else:
            self.rtn_value = self.stack[self.idx-1]
            self.idx -= 1
            return self.rtn_value

우선, idx가 0 이하인 경우 ( 리스트 안에 아무것도 없는 경우)에는 -1를 반환한다.

그리고 빼기 전 stack[idx] 값을 rtn_value에 저장하고, idx를 1 감소시키고, rtn_value를 반환한다.

(다만, 이 경우에는 여전히 stack 에 pop할 value가 여전히 남아있게되는 문제점이 있다. 만약 pop의 목적이 리스트에서 value를 완전히 제거시키는 것에 있다면 다른 방법을 취해야 할 것이다.)

 

size는 다음과 같이 구성된다.

    def size(self):
        return self.idx

간단하게 현재 idx를 표시하면 그것이 보관하고 있는 정수의 개수가 된다.

 

 

empty는 다음과 같이 구성된다.

    def empty(self):
        if self.idx <= 0:
            return 1
        else:
            return 0

size와 동일하다. idx를 기준으로 idx가 0이라면 (오류가 나서 idx가 음수로 가는 경우도 생각하여 <= 를 넣었다.) 1을 반환하고, 아니면 0을 반환한다.

 

top은 다음과 같이 구성된다.

    def top(self):
        if self.idx <= 0:
            return -1
        else:
            return self.stack[self.idx-1]

여기도 비슷하게, idx가 0이하인 경우(stack에 value가 없는 경우)에는 -1를 반환하고, 아니면 stack의 idx가 표시하는 value를 표시한다. 

 

그리고 아래와 같이 입력을 받도록한다.

def order(menu):
    global stack
    if menu[0] == "push":
        stack.push(menu[1])
    
    elif menu[0] == "pop":
        print(stack.pop())

    elif menu[0] == "size":
        print(stack.size())

    elif menu[0] == "empty":
        print(stack.empty())

    elif menu[0] == "top":
        print(stack.top())


stack = MyStack()
t = int(sys.stdin.readline())
for i in range(t):
    
    menu = sys.stdin.readline().split( )
    order(menu)

 

처음 제출했을 때, 파이파이로도 시간초과가 떠서 어리둥절 했는데, input을 readline으로 바꿨더니, 파이썬으로도 통과가 되었다.

 

생각보다 엄청난 차이가 나나보다. 이제 무조건 readline 써야겠다 ㅠ.ㅠ