[99클럽 4기 코테 스터디 TIL 12일차] 스택 (feat. Stack 자료구조, String.startsWith())

https://aliencoder.tistory.com/m/148

 

• 스택 자료구조를 이해하고 푸는 문제이다.
• 스택 자료구조를 직접 구현해서 그에 맞는 메소드를 호출해 사용하라고 이해하였다.
• 그리하여 챗gpt의 도움을 좀 받아 아래와 같이 스택을 구현하고, 입력받은 숫자 및 메소드 대로 출력하는 로직을 구현했다.
• 내가 만든 MadeStack 클래스는 static으로 만들었다.
• Stack 클래스를 호출해 만들어도 되었을 텐데.. 추가구현코드에서 확인하자

1)  내가 구현한 코드

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine()); //명령의 수

        MadeStack stack = new MadeStack(N);

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            String method = "";
            String num = "";
            if (str.contains(" ")) {
                method = str.split(" ")[0];
                num = str.split(" ")[1];
            } else {
                method = str;
            }

            switch (method) {
                case "push":
                    stack.push(Integer.parseInt(num));
                    break;
                case "pop":
                    bw.write(""+stack.pop()+"\n");
                    break;
                case "size":
                    bw.write(""+stack.size()+"\n");
                    break;
                case "empty":
                    bw.write(""+stack.empty()+"\n");
                    break;
                case "top":
                    bw.write(""+stack.top()+"\n");
                    break;
            }
        }
        bw.flush();

        br.close();
        bw.close();

    }
    static class MadeStack{
        private int maxsize;
        private int[] stackArray; // 스택 배열
        private int topIdx; // 스택의 가장 상단 위치를 나타냄

        // 생성자
        public MadeStack(int num) {
            this.maxsize = num;
            this.stackArray = new int[maxsize];
            this.topIdx = -1; // 초기화할 때 스택은 비어 있음
        }

        //push X: 정수 X를 스택에 넣는 연산
        public void push(int value) {
            stackArray[++topIdx] = value;
        }
        //pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
        public int pop() {
            if(topIdx == -1) return -1;
            int answer = stackArray[topIdx];
            stackArray[topIdx--] = 0;
            return answer;
        }
        //size: 스택에 들어있는 정수의 개수를 출력한다.
        public int size(){
            return topIdx+1;
        }
        //empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
        public int empty() {
            if (topIdx == -1) return 1;
            return 0;
        }
        //top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
        public int top() {
            if(topIdx == -1) {
                return -1;
            } else{
                return stackArray[topIdx];
            }
        }
    }


}

 

 

2) 추가 구현 코드

Stack.push()

• 설명: 스택에 새로운 요소를 추가
• 동작: 새로 추가된 요소는 항상 스택의 최상단에 위치
• 예시

stack.push(5); //스택의 최상단에 5가 추가

 

Stack.pop()

• 설명: 스택에서 가장 상단에 있는 요소를 제거하고 반환
• 동작: 스택이 비어 있으면 보통 예외를 발생시키거나, 특정 값(예: -1 또는 null)을 반환
• 예시

int top = stack.pop(); //스택 최상단의 값을 가져온 후 스택에서 제거

 

Stack.peek()  & Stack.top()

• 설명: 스택의 최상단에 있는 요소를 반환하지만, 스택에서 제거하지 않음
• 동작: pop과 달리 요소를 제거하지 않고 단순히 확인, 스택이 비어 있을 때 특정 값을 반환하거나 예외 발생 가능
• 예시

int topElement = stack.peek(); //스택의 최상단 요소를 반환하지만 제거하지 않음

 

Stack.isEmpty()

• 설명: 스택이 비어 있는지를 확인
• 동작: 스택에 요소가 없으면 true, 하나 이상의 요소가 있으면 false를 반환
• 예시

 if(stack.isEmpty()) { ... } //스택이 비어 있는지 확인하는 조건문

 

Stack.size()

• 설명: 스택에 들어있는 요소의 개수를 반환.
• 동작: 현재 스택에 쌓여 있는 요소의 개수를 반환
• 예시

int count = stack.size(); //스택의 요소 개수를 반환

.

추가 메서드 (일부 언어/라이브러리에서 제공)

스택 자료구조의 경우 기본적인 기능은 위의 다섯 가지 메서드가 대부분을 차지하지만,

일부 언어 또는 라이브러리에서는 다음과 같은 추가 메서드를 제공함

• clear: 스택의 모든 요소를 제거하여 비움
• contains(Object o): 특정 요소가 스택에 존재하는지 확인함
• search(Object o): 특정 요소의 위치를 반환함, 스택의 최상단을 1로 계산하여, 요소의 상대적 위치를 반환함

import java.io.*;
import java.util.*;

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 command = br.readLine();

			//push 명령은 push 문자열로 시작하므로 split을 사용하여 값을 추출한 후 스택에 추가한다.
            if (command.startsWith("push")) {
                int X = Integer.parseInt(command.split(" ")[1]);
                stack.push(X);
            //스택이 비어 있으면 -1을 출력하고, 그렇지 않으면 pop 메서드를 호출해 최상단 값을 제거하고 출력한다.
            } else if (command.equals("pop")) {
                bw.write((stack.isEmpty() ? -1 : stack.pop()) + "\n");
            //size 메서드를 호출하여 스택의 크기를 출력한다.
            } else if (command.equals("size")) {
                bw.write(stack.size() + "\n");
            //스택이 비어 있으면 1을, 그렇지 않으면 0을 출력한다.
            } else if (command.equals("empty")) {
                bw.write((stack.isEmpty() ? 1 : 0) + "\n");
            //스택이 비어 있으면 -1을 출력하고, 비어 있지 않으면 peek 메서드로 최상단 값을 출력한다.
            } else if (command.equals("top")) {
                bw.write((stack.isEmpty() ? -1 : stack.peek()) + "\n");
            }
        }

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

 

 

 

3) 오늘의 회고

문제점

• 명령어 파싱에서 push와 pop을 처리하는 부분을 고려해야 했다.

해결법

• split과 startsWith를 사용해 명령어를 효율적으로 파싱하고 분기 처리했다.

새롭게 알게 된 점

• BufferedReader와 BufferedWriter를 사용해 효율적으로 많은 입력과 출력을 처리할 수 있다는 점을 배웠다.

내일의 학습 목표

• 명령어 파싱과 스택 관련 문제들을 다른 자료구조와 결합하여 확장해 보려고 한다.

 

 

4) 추가 문제

미들러 - 토마토

https://www.acmicpc.net/problem/7569

챌린저 - 도넛과 막대 그래프

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스