on
[백준알고리즘-JAVA]10828번 풀이(스택) - 초보도 이해하는 풀이
[백준알고리즘-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 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("
"); else sb.append(stk.pop()).append("
"); } else if(command.equals("size")) { sb.append(stk.size()).append("
"); } else if(command.equals("empty")) { if(stk.isEmpty()) sb.append(1).append("
"); else sb.append(0).append("
"); } else if(command.equals("top")) { if(stk.isEmpty()) sb.append(-1).append("
"); else sb.append(stk.peek()).append("
"); } } System.out.println(sb); } }
뭐 이버 스택은 스택의 기본적인 구조를 파악하기 위한 문제이다. 스택만 구현할 줄 안다면, 쉽게 구현할 수 있는 문제이다.
STEP을 따라서 하나씩 이해해보도록 하자
알고리즘 흐름도
입력받기 -> 입력에 따른 출력 결정해 주기 -> 출력하기
- 간단히 먼저 선언하는 스택은 아래처럼 선언하면 됩니다.
Stack 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("
"); else sb.append(stk.pop()).append("
");
po구현도 비어있을 경우에만, 예외처리를 해준다면, 어려울 것이 없습니다. 비어있다면, -1 아니면 stk에서 pop을 해줍니다. 즉 가장 위에 있는 값을 빼와주는 것이지요
STEP 3 SIZE 구현하기
else if(command.equals("size")) { sb.append(stk.size()).append("
");
이건 뭐 진짜 아무것도 없습니다. 기본적으로 배열과 같이 size를 사용하죠
STEP 4 empty 구현하기
else if(command.equals("empty")) { if(stk.isEmpty()) sb.append(1).append("
"); else sb.append(0).append("
");
비어있는 것도 금방 확인하죠. 비어있다면 1 아니라면 0 이것 또한 배열과 비슷하죠 ㅎㅎ 크게 어려울 것 없습니다.
STEP 5 top 구현하기
else if(command.equals("top")) { if(stk.isEmpty()) sb.append(-1).append("
"); else sb.append(stk.peek()).append("
");
마지막으로 구현할 것은 top 꼭대기에 값이 있으면 peek라는 함수를 통해서 수 비게 꺼낼 수 있으며 만약 스택이 비어있다면 -1을 출력해 줍니다~
STEP6 스택의 간단한 이해
스택에 대해서 잘 모르신다면 기본적으로 LIFO만 기억하시면 됩니다. 나중에 들어온 게 먼저 나간다 ㅎㅎ 하나의 바구니라고 생각합시다. 책을 한 권 한 권 쌓아두면 아래 것을 꺼내기 위해서는 위에서부터 하나씩 빼야 되죠. 이런 느낌입니다~
from http://infodon.tistory.com/91 by ccl(A) rewrite - 2021-09-16 12:01:03