스택
-
[백준]2493: 탑 - JAVA문제풀이/백준 2021. 5. 1. 14:25
[백준]2493: 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 자료구조 관련 문제로 볼 수 있을 것 같다. 문제는 어렵지 않으나 메모리, 시간 초과가 발생하지 않도록 적절한 자료구조를 사용해 주어야 한다. 우선 문제의 조건을 분석해 보면, 탑의 높이를 입력 받고 나서 레이저를 자신 보다 앞의 인덱스의 탑에만 송신한다. 즉, 탑을 미리 입력을 받지 않고 입력 받으면서 이미 입력 받은 값들 하고와 비교하여도 충분히 문제를 풀 수 있다는 것이다. 이..
-
[백준]1918: 후위 표기식 - JAVA문제풀이/백준 2021. 2. 28. 16:20
[백준]1918: 후위 표기식 www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 풀이 후위 표기식 문제이다! 개념상으로는 알고 있었는데 구현하는 방법을 까먹어서 예제 입력을 따라가보면서 어떻게 구현할지 생각해 보았고, 숫자가 들어오면 그대로 출력하고, 연산자가 들어오면 스택에 담아서 괄호와 우선순위 연산을 하면서 출력해 주면 된다는 결론을 얻엇다. 1. 괄호 연산 - 연산자 입력으로 괄호가 들어왔을 때는 다음과 같이 처리한다. case 1) '('괄호..
-
자료구조 - StackCS/자료구조 2021. 2. 17. 21:22
Stack stack 자료구조 후입선출 알고리즘으로 나중에 들어온 데이터를 먼저 반환한다. 시간 복잡도 insert: O(1) delete: O(1) search: O(n) 구현 with JAVA 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 public class Stack { private int top; private int size; private int[] arr; //생성자 public stack(int size) { top = -1; this.size = size; arr = new int[size]; } pu..