자료구조 :: 스택으로 풀 수 있는 문제

엘리스 코딩 자료구조에서 배운 내용

 

 

stack(스택)

class Stack:
    '''
    이전 실습에서 작성한 Stack 클래스 코드를 사용합니다.
    '''
    def __init__(self) :
        '''
        자료를 저장할 공간(리스트) myStack을 만듭니다.
        '''
        self.myStack = []

    def push(self, n) :
        '''
        stack에 정수 n을 넣습니다.
        '''
        self.myStack.append(n)

    def pop(self) :
        '''
        stack에서 가장 위에 있는 정수를 제거합니다. 만약 stack에 아무 원소가 없다면 아무 일도 하지 않습니다.
        '''
        if self.empty() == 1:
            return
        self.myStack.pop()

    def size(self) :
        '''
        stack에 들어 있는 정수의 개수를 return 합니다.
        '''
        return len(self.myStack)

    def empty(self) :
        '''
        stack이 비어있다면 1, 아니면 0을 return 합니다.
        '''
        if self.size() == 0:
            return 1
        else :
            return 0

    def top(self) :
        '''
        stack의 가장 위에 있는 정수를 return 합니다. 만약 stack에 들어있는 값이 없을 경우에는 -1을 return 합니다.
        '''
        if self.empty() == 1:
            return - 1
        return self.myStack[-1]

 

스택으로 풀 수 있는 문제

 

올바른 괄호인지 판단

()()() => YES

((())) => YES

()) => NO

 

특징

• 여는 괄호는 스택에 넣고, 닫는 괄호는 스택에서 괄호 하나 제거(pop)
• 모든 괄호 처리하고 스택 비어 있으면 올바른 괄호
• 스택 비어있을 때 닫은 괄호 들어오면 올바르지 않은 괄호

 

스택으로 수열 만들기

규칙

• 1부터 N까지 모든 정수 한 번씩 스택에 입력하고 출력
• 무조건 작은 수는 큰 수보다 먼저 입력

예) 1보다 3이 먼저 입력되는 경우 없다

 

1 2 3 4 입력으로

2 1 4 3 만들 수 있나? => YES

 

1 2 3 4 입력으로

3 1 2 4 만들 수 있는가? => NO

 

 

메모장

elice

메모장 명령어

L - 왼쪽으로 커서 한 칸

R - 오른쪽으로 커서 한 칸

D - 커서 왼쪽 문자 하나 삭제

P s - 알파벳 s 커서 왼쪽에 추가

 

커서를 기준으로

왼쪽 문자열과 오른쪽 문자열을 각각 스택으로 저장

L - 왼쪽 스택 알파벳 제거 => 오른쪽 스택에 추가

R -  오른쪽 스택 알파벳 제거 => 왼쪽 스택에 추가

D - 왼쪽 스택 알파벳 제거

P - 왼쪽 스택 알파벳 추가