[알고리즘][BAEKJOON][JAVA][Python]10828번, 스택

📑 이번 문제는 Stack 문제이다.

문제를 풀기전에 일단 Stack이 무엇인지 알아보는 시간을 가져볼까 한다.

1. Stack이란?

📌스택(Stack)이란?

• 사전적 정의 : '쌓다', '더미' 와 같다라고 생각하면 된다.
• 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.
• 스택(Stack)은 LIFO(Last In First Out) 을 따른다. 즉 '선입후출' '후입선출'이라는 개념이다. 먼저 들어간 것은 나중에 나갈 수 있고, 나중에 들어간 것은 먼저 나갈 수 있는 것이다.
  
  출처 : 위키백과

이렇게만 보면 무슨말인지 이해하기 굉장히 어렵다😅

그래서 우리는 쉬운 예로 '프링글스' 를 생각하면 편하다.
위에 있는 감자칩을 먹어야, 그 아래의 감자칩을 먹을 수 있고, 감자칩을 통 속에 넣을 때는 중간에 끼워 넣을 수 없다.
이렇게 쌓아가는 것이 Stack(스택)이다.

그림을 통해 Stack을 자세하게 살펴 보겠다.

1. 스택의 연산

📌 스택(Stack)의 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

2. 스택(Stack)의 사용 사례

• 재귀 알고리즘
• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
• 후위 표기법 계산

이 정도로 이해하고 이젠 Stack을 Java와 Python으로 구현해보도록 하겠다.

2. JAVA

1. 배열을 사용하여 직접 Stack 클래스 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Stack{
	private int top;
	private int stackArr[];
	
	public Stack(int size) {
		this.top = -1;
		this.stackArr = new int[size];
	}
	
	public void push(int x) {
		this.stackArr[++top] = x;
	}

	public int pop() {
		if(top == -1) return -1; 
		return this.stackArr[top--];
	}

	public int size() {
		return this.top + 1; 
	}

	public int empty() {
		if(top == -1) return 1;
		return 0;
	}

	public int top() {
		if(top == -1) return -1;
		else return this.stackArr[top];
	}
}

public class Main { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());

		Stack stack = new Stack(n);

		for(int i = 0;i<n;i++) {
			String cons = br.readLine();
			if(cons.contains("push")) {
				String spt[] = cons.split(" ");
				stack.push(Integer.parseInt(spt[1]));
			}
            		else if(cons.contains("pop")) { 
				bw.write(String.valueOf(stack.pop())+"\n"); 
			}
            		else if(cons.contains("size")) {				
                    		bw.write(String.valueOf(stack.size())+"\n");
			}
            		else if(cons.contains("empty")) {
				bw.write(String.valueOf(stack.empty())+"\n"); 
			}
            		else if(cons.contains("top")) {
				bw.write(String.valueOf(stack.top())+"\n");
			}
		}
		
		bw.flush();
		bw.close();		
		br.close();
	     
	}

}

2. Stack 라이브러리를 활용하여 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());

		Stack<Integer> stack = new Stack<>();
		
		for(int i=0; i<n; i++) {
			String cons = br.readLine();
			
			if(cons.contains("push")) {
				String spt[] = cons.split(" ");
				stack.push(Integer.parseInt(spt[1]));
			}
            		else if(cons.contains("pop")) {
				if(stack.empty()) bw.write(-1+"\n");		
				else bw.write(stack.pop()+"\n");			
			}
            		else if(cons.contains("size")) {
				bw.write(stack.size()+"\n");
			}
            		else if(cons.contains("empty")) {
				if(stack.empty()) bw.write(1+"\n");
				else bw.write(0+"\n");
			}
            		else if(cons.contains("top")) {
				if(stack.empty())bw.write(-1+"\n");								
				else bw.write(stack.peek()+"\n");
			}
		}
		
		bw.flush();
		bw.close();		
		br.close();
	     
	}

}

3. Python

python은 따로 Stack 구조를 제공하지 않으므로 기본 클래스 List를 이용하여 표현이 가능하다.

import sys

def push(x):
    stack.append(x)

def pop():
    if(not stack):
        return -1
    else:
        return stack.pop()

def size():
    return len(stack)

def empty():
    return 0 if stack else 1

def top():
    return stack[-1] if stack else -1

N = int(sys.stdin.readline().rstrip())
stack = []

for _ in range(N):
    input_split = sys.stdin.readline().rstrip().split()

    com = input_split[0]

    if com == "push":
        push(input_split[1])
    elif com == "pop":
        print(pop())
    elif com == "size":
        print(size())
    elif com == "empty":
        print(empty())
    elif com == "top":
        print(top())

처음에는 input을 사용했더니 런타임 오류로 계속 실패가 떠서 구글링을 해보니 입출력 속도 또한 비교를 해주어야하는 문제였다.

✔입출력 속도 비교 : sys.stdin.readline > raw_input() > input()