[알고리즘/백준] 10828번 : 스택

문제	10828번 : 스택
문제링크	https://www.acmicpc.net/problem/10828
난이도	S4
언어	Java
분류	자료구조 | 구현, 자료구조, 스택

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

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

        // 입력 - 명령의 수
        int n = Integer.parseInt(br.readLine());

        // 스택
        ArrayList<Integer> stack = new ArrayList<Integer>(n);

        // 명령어 반복
        for(int i = 0; i < n; i++){
            String input = br.readLine(); // 명령어 종류
            String[] parts = input.split(" ");

            switch (parts[0]){
                case "push" :
                    int data = Integer.parseInt(parts[1]);
                    stack.add(data);
                    break;
                    
                case "pop" :
                    // 스택이 비어있을 경우
                    if(stack.isEmpty()) {
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(stack.get(stack.size() -1) + "\n");
                        stack.remove(stack.size() -1);
                    }
                    break;
                    
                case "size" :
                    bw.write(stack.size() + "\n");
                    break;
                    
                case "empty" :
                    if (stack.isEmpty()) {
                        // 스택이 비어있을 경우
                        bw.write("1" + "\n");
                    } else {
                        bw.write("0" + "\n");
                    }
                    break;
                    
                case "top" :
                    if (stack.isEmpty()) {
                        // 스택이 비어있을 경우
                        bw.write("-1" + "\n");
                    } else {
                        bw.write(stack.get(stack.size()-1) + "\n");
                    }
                    break;
            }
        }

        bw.flush();
        bw.close();
    }
}

📌 구해야 하는 정답

명령어에 대한 결과

- push x : 스택에 x 넣기

- pop : 스택 맨 위의 수 빼고 출력, 없을 경우 -1 출력

- size : 스택에 있는 정수 개수 출력

- empty : 스택 비어있으면 1, 아니면 0 출력

- top : 스택 맨 위 정수 출력 없을 경우 -1 출력

📌 풀이하기

1. 입력받기

// 입력 - 명령의 수
int n = Integer.parseInt(br.readLine());

String input = br.readLine(); // 명령어 종류
String[] parts = input.split(" ");

 

2. 스택 계산 & 결과 출력

for(int i = 0; i < n; i++){
    String input = br.readLine(); // 명령어 종류
    String[] parts = input.split(" ");

    switch (parts[0]){
        case "push" :
            int data = Integer.parseInt(parts[1]);
            stack.add(data);
            break;

        case "pop" :
            // 스택이 비어있을 경우
            if(stack.isEmpty()) {
                bw.write("-1" + "\n");
            } else {
                bw.write(stack.get(stack.size() -1) + "\n");
                stack.remove(stack.size() -1);
            }
            break;

        case "size" :
            bw.write(stack.size() + "\n");
            break;

        case "empty" :
            if (stack.isEmpty()) {
                // 스택이 비어있을 경우
                bw.write("1" + "\n");
            } else {
                bw.write("0" + "\n");
            }
            break;

        case "top" :
            if (stack.isEmpty()) {
                // 스택이 비어있을 경우
                bw.write("-1" + "\n");
            } else {
                bw.write(stack.get(stack.size()-1) + "\n");
            }
            break;
    }
}

 

📌 시간 복잡도

각 명령어의 시간복잡도는 각 항목에서 확인하실 수 있습니다.

추가로 스택 자료구조의 대표적인 연산들의 시간복잡도는 아래와 같습니다.

 

문제 푸는 방식이 여러개인데, 이번에는 ArrayList를 이용해서 해결하였다.