[백준_Stack]10828번_스택
다양한 알고리즘을 접하기 전에, 기본에 충실하기 위해 Stack을 정복하기로 하였다.
많은 사람들이 이미 알고 있는 것 처럼, Stack의 특징은 First In Last Out(FILO)이다.
즉, 마지막에 들어온게 가장 먼저 나가는 자료구조라고 할 수 있다.
대표적으로 후위표기법 계산에 스택이 사용될 수 있겠다.
그렇다면 먼저 아래 문제를 풀어보도록 하자.
백준 홈페이지의 10828문제인 Stack 관련 문제이다.
PUSH는 Stack에 값을 입력할 때, POP은 Stack의 가장 위에 있는 값을 출력할 때 사용되는 메서드이다.
위 문제는 Java의 Stack 클래스를 사용하면 아주 쉽게 풀 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Al10828 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int testCase = Integer.parseInt(br.readLine()); Stack<Integer> stack = new Stack<>(); StringTokenizer token; StringBuilder build = new StringBuilder(); for (int i = 0; i < testCase; i++) { token = new StringTokenizer(br.readLine()); String method = token.nextToken(); switch(method) { case "push" : int temp = Integer.parseInt(token.nextToken()); stack.push(temp); break; case "pop" : if(stack.isEmpty()) build.append(-1 + "\n"); else build.append(stack.pop() + "\n"); break; case "size" : build.append(stack.size()+"\n"); break; case "empty" : if(stack.isEmpty()) build.append(1 + "\n"); else build.append(0 + "\n"); break; case "top" : if(stack.isEmpty()) build.append(-1 + "\n"); else build.append(stack.peek() + "\n"); break; } } System.out.println(build.toString()); } } | cs |
그렇다면 이번에는 Stack을 직접 구현해보도록 하자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Al10828 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int size = Integer.parseInt(br.readLine()); Custom_Stack stack = new Custom_Stack(size); StringTokenizer token; StringBuilder build = new StringBuilder(); for (int i = 0; i < size; i++) { token = new StringTokenizer(br.readLine()); String method = token.nextToken(); switch(method) { case "push" : stack.push(Integer.parseInt(token.nextToken())); break; case "pop" : build.append(stack.pop() + "\n"); break; case "empty" : build.append(stack.empty() + "\n"); break; case "size" : build.append(stack.size() + "\n"); break; case "top" : build.append(stack.top() + "\n"); break; } } System.out.println(build.toString()); } /* 배열을 이용한 Stack class */ public static class Custom_Stack{ int[] stack; int point = 0; /* make stack */ public Custom_Stack(int size) { this.stack = new int[size]; } /* push method */ public void push(int x) { if(point >= stack.length) return; // stack overflow; stack[point] = x; point++; } /* pop method */ public int pop() { if(point-1 < 0) return -1; // stack underflow; int val = stack[point-1]; point--; return val; } /* return stack size method */ public int size() { return point; } /* check stack status method */ public int empty() { if(point == 0) return 1; else return 0; } /* return stack's top value method */ public int top() { if(point == 0) return -1; else return stack[point-1]; } } } | cs |
배열로 Stack을 구현하여 문제를 풀어 봤다
위에가 배열로 직접 구현한 Stack, 아래가 Stack 자료구조를 사용한 결과이다.
어서 더 어려운 문제들을 풀어봐야지!
'Algorithms' 카테고리의 다른 글
| [백준_Queue]1966번_프린터 큐 (0) | 2018.11.18 |
|---|---|
| [백준_Queue]10845번_큐 (0) | 2018.11.13 |
| [백준_Stack]1874번_스택 수열 (0) | 2018.11.11 |
| [백준_Stack]2504번_괄호의 값 (0) | 2018.11.06 |
| [백준_Stack]9012번_괄호 (0) | 2018.11.04 |