백준 10828번-스택(JAVA)

www.acmicpc.net/problem/10828

10828번: 스택

자료구조 중 하나인 '스택'을 구현하는 문제입니다.

 

정수를 저장하는 '스택'과 다음 메소드들을 구현합니다.

첫 번째 줄에는 입력할 명령어의 개수 N을 받고, 그 다음부터 입력받는 명령어에 따라

스택의 메소드들을 실행하는 문제 입니다.

 

▶push X: 정수 X를 스택에 넣는 연산이다.

▶pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는

          -1을 출력한다.

▶size: 스택에 들어있는 정수의 개수를 출력한다.

▶empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

▶top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

 

먼저 스택에 대해 간단히 알아본 후 하나하나 뜯어보겠습니다.

 

---

스택(Stack)

스택에 데이터를 추가 때는 가장 위에 추가되고,

데이터를 꺼낼 때는 가장 위에서부터 빠지게 됩니다.

 

아래와 같이 데이터가 3개 들어있는 스택이 있다고 가정합니다.

 

 

여기에 데이터를 하나 추가합니다.

스택에 데이터를 추가하는 동작을 push라고 합니다.

추가된 데이터는 스택의 가장 위에 쌓입니다.

 

가장 최근에 추가된 데이터, (이 그림에서는 new)를 top이라고 합니다.

 

 

다시 데이터를 하나 꺼냅니다. 이 동작을 pop이라고 합니다.

pop을 실행하면 스택의 가장 위에 쌓인 데이터부터(가장 최근에 추가된 데이터) 차례대로 꺼냅니다.

이렇게 나중에 넣은 것을 먼저 꺼내는 구조를 후입선출, 

'Last In First Out' 이라고 합니다. (LIFO)

 

---

다시 문제로 돌아와봅니다.

우선 Main에서 명령어를 입력 받는건 생각하지 않고, 스택으로 쓸 클래스를 구현합니다.

 

class Stack {
    private BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private int[] stack;
    private int size=0;


    public int lastIndex(){
        return this.size-1;
    }

    public void push(int x){
        int[] newArr=new int[this.size+1];

        if(this.size>0){
            this.size++;
            System.arraycopy(stack,0,newArr,0,lastIndex());
            stack=newArr;
            stack[lastIndex()]=x;
        }else{
            this.size++;
            stack=newArr;
            stack[lastIndex()]=x;
        }
    }

    public void pop() throws IOException{
        top();
        if(size>0){
            int[] newArr = new int[size-1];
            this.size--;
            newArr= Arrays.copyOf(stack,size);
            stack=newArr;
        }

    }

    public void size() throws IOException{
        bw.write(this.size+"\n");
        bw.flush();
    }

    public void empty() throws IOException{
        if(size>0){
            bw.write(0+"\n");
        }else{
            bw.write(1+"\n");
        }
        bw.flush();
    }

    public void top() throws IOException{
        if(size>0){
            bw.write(stack[lastIndex()]+"\n");
        }else{
            bw.write(-1+"\n");
        }
        bw.flush();
    }
}

필드

* private BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

 스택내의 출력을 BufferedWriter로 하도록 생성해줍니다.

* private int[] stack;

 스택으로 사용할 int 배열입니다. 

* private int size=0;

 스택의 (int[] stack) 크기를 저장할 변수입니다.

 Stack 인스턴스를 생성한다고 바로 스택을 생성하지 않을 것이므로 초기값을 0으로 둡니다.

 

 

메소드

* +lastIndex() : int

  스택의 마지막 인덱스를 구해줄 메소드입니다.

  문제에는 없지만 자주 쓰일 것이므로 추가했습니다.

 public int lastIndex(){
        return this.size-1;
    }

 

* +push(int): void

▶push X: 정수 X를 스택에 넣는 연산이다.

 public void push(int x){
        int[] newArr=new int[this.size+1];

        if(this.size>0){
            this.size++;
            System.arraycopy(stack,0,newArr,0,lastIndex());
            stack=newArr;
            stack[lastIndex()]=x;
        }else{
            this.size++;
            stack=newArr;
            stack[lastIndex()]=x;
        }
    }

 

 

push를 할때마다 stack의 크기가 하나 늘어나고, 마지막 인덱스에는 x가 들어와야 합니다.

일단은 기존의 stack 배열을 덮어씌울 새 int배열 newArr을 생성합니다.

크기는 하나 늘어나야하니 기존size+1 이 됩니다.

 

그리고 기존에 stack이 생성되어 있을 경우와 생성되지 않았을 경우를 조건처리 합니다.

이는 size의 값으로 알 수 있습니다.

 

-생성되었을 경우

 size를 1 늘립니다.

 System.arraycopy 메소드를 통해 기존의 stack배열에 있던 값을 newArr에 복사해줍니다.

 기존 stack을 newArr로 바꾸고, 가장 마지막 인덱스에는 새로 입력받은 x를 대입해줍니다. 

 

-생성되지 않았을 경우

 size를 1 늘립니다.

 기존 stack을 newArr로 바꾸고, 가장 마지막 인덱스에는 새로 입력받은 x를 대입해줍니다. 

 

* +top(): void

▶top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는

         -1을 출력한다.

(문제에 나온 순서대로 정리하려 했는데 pop()에서 top()을 활용할 것이므로 먼저 작성합니다.)

public void top() throws IOException{
        if(size>0){
            bw.write(stack[lastIndex()]+"\n");
        }else{
            bw.write(-1+"\n");
        }
        bw.flush();
    }

stack이 생성되어있다면 가장 마지막 인덱스를 버퍼에 쓰고, 아니라면 -1을 버퍼에 쓰고

조건문을 빠져나와 flush()로 출력해줍니다.

 

* +pop(): void

▶pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.

          만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

public void pop() throws IOException{
        top();
        if(size>0){
            int[] newArr = new int[size-1];
            this.size--;
            newArr= Arrays.copyOf(stack,size);
            stack=newArr;
        }

    }

위의 top메소드를 활용해 일단 조건에 따라 출력하도록 합니다.

stack이 생성되어 있을 경우엔 마지막 인덱스 값을 삭제해야 하므로

size-1 크기의 새 int 배열을 생성, size값을 1 빼고

newArr에는 기존 stack의 size(위에서 1이 빠졌으니 빠진 개수)만큼 복제를 합니다.

stack을 newArr로 바꿉니다.

 

* +size(): void

▶size: 스택에 들어있는 정수의 개수를 출력한다.

 public void size() throws IOException{
        bw.write(this.size+"\n");
        bw.flush();
    }

간단히 stack의 크기를 저장하는 필드 size값을 출력합니다.

 

* +empty(): void

▶empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

 public void empty() throws IOException{
        if(size>0){
            bw.write(0+"\n");
        }else{
            bw.write(1+"\n");
        }
        bw.flush();
    }

역시 size 값에 따라 출력해줍니다.

 

 

---

이제 Main에서 입력을 받아봅니다.

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        //10828
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Stack st = new Stack();

        while(N>0){
            String[] command = br.readLine().split(" ");

            switch (command[0]){
                case "push":st.push(Integer.parseInt(command[1]));break;
                case "pop": st.pop();break;
                case "size": st.size();break;
                case "empty": st.empty();break;
                case "top": st.top();break;
                default:break;
            }
            N--;
        }

    }

}

 

풀이과정

1. 입력을 받을 수 있도록 BufferedReader를 생성합니다.

   int N에 입력받을 명령어의 개수를 받습니다.

 

2. 스택을 사용하기 위해 위에서 생성한 Stack클래스의 인스턴스를 생성합니다.

 

3. N만큼 반복해서 명령어를 입력받기 위해 while문을 생성합니다.(한번 돌때마다 N--)

   

   명령어가 push일 경우, "push 1"로 들어올 것이기 때문에

   String배열에 입력받은 값을 split으로 잘라서 받습니다.

   

   switch문을 통해 명령어에 따라 Stack의 메소드가 실행되도록 합니다.