[백준알고리즘-JAVA]10828번 풀이(스택) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 10828번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 10828 (스택)

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

 

명령은 총 다섯 가지이다.

 

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

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

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

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

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

입력 출력 예제

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int T;
	

	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		Stack<Integer> stk = new Stack<>();
		
		for(int i = 0 ; i < T ;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			String command = st.nextToken();
			
			if(st.hasMoreTokens()) {
				stk.push(Integer.parseInt(st.nextToken()));
			} else if(command.equals("pop")) {
				if(stk.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(stk.pop()).append("\n");
			} else if(command.equals("size")) {
				sb.append(stk.size()).append("\n");
			} else if(command.equals("empty")) {
				if(stk.isEmpty())
					sb.append(1).append("\n");
				else
					sb.append(0).append("\n");
			} else if(command.equals("top")) {
				if(stk.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(stk.peek()).append("\n");
			}
		}
	
		System.out.println(sb);

		}
	
	
}

뭐 이버 스택은 스택의 기본적인 구조를 파악하기 위한 문제이다. 스택만 구현할 줄 안다면, 쉽게 구현할 수 있는 문제이다.

 

 STEP을 따라서 하나씩 이해해보도록 하자

---

알고리즘 흐름도

 입력받기 -> 입력에 따른 출력 결정해 주기 -> 출력하기

 

 

- 간단히 먼저 선언하는 스택은 아래처럼 선언하면 됩니다.

		Stack<Integer> stk = new Stack<>();

---

STEP1 PUSH 구현하기

			String command = st.nextToken();
			
			if(st.hasMoreTokens()) {
				stk.push(Integer.parseInt(st.nextToken()));
			}

뭐 아주 간단합니다. st는 StringTokenizer로 구현하였고, 만약에 토큰을 하나 꺼냈는데 하나 더 남아있다면, push라는 의미이죠. 그렇다면 미리 선언해준 stk 스택에 push 밀어줍니다. 그 토큰을

---

STEP2 POP 구현하기

 else if(command.equals("pop")) {
				if(stk.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(stk.pop()).append("\n");

po구현도 비어있을 경우에만, 예외처리를 해준다면, 어려울 것이 없습니다. 비어있다면, -1 아니면 stk에서 pop을 해줍니다. 즉 가장 위에 있는 값을 빼와주는 것이지요

---

STEP 3 SIZE 구현하기

 else if(command.equals("size")) {
				sb.append(stk.size()).append("\n");

이건 뭐 진짜 아무것도 없습니다. 기본적으로 배열과 같이 size를 사용하죠

---

STEP 4 empty 구현하기

else if(command.equals("empty")) {
				if(stk.isEmpty())
					sb.append(1).append("\n");
				else
					sb.append(0).append("\n");

비어있는 것도 금방 확인하죠. 비어있다면 1 아니라면 0 이것 또한 배열과 비슷하죠 ㅎㅎ 크게 어려울 것 없습니다.

---

STEP 5 top 구현하기

else if(command.equals("top")) {
				if(stk.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(stk.peek()).append("\n");

마지막으로 구현할 것은 top 꼭대기에 값이 있으면 peek라는 함수를 통해서 수 비게 꺼낼 수 있으며 만약 스택이 비어있다면 -1을 출력해 줍니다~

---

STEP6  스택의 간단한 이해

 스택에 대해서 잘 모르신다면 기본적으로 LIFO만 기억하시면 됩니다. 나중에 들어온 게 먼저 나간다 ㅎㅎ 하나의 바구니라고 생각합시다. 책을 한 권 한 권 쌓아두면 아래 것을 꺼내기 위해서는 위에서부터 하나씩 빼야 되죠. 이런 느낌입니다~