1. 스택
1. 스택이란?
한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In Frist Out) 형식의 자료구조이다.
- push : 스택에 자료를 넣는 연산
- pop : 스택에서 자료를 빼는 연산
- top : 스택의 가장 위에 있는 자료를 보는 연산
- empty : 스택이 비어있는지 아닌지를 알아보는 연산
- size : 스택에 저장되어있는 자료의 개수를 알아보는 연산
2. 스택 구현
2.1 일차원 배열 하나로 구현한다.
int stack[100000]; int size = 0;size는 초기에 데이터가 없으므로 0으로 초기화한다.
2.2 push
public void push(int data){ stack[size] = data; size += 1; }2.3 pop
public int pop() { stack[size-1] = 0; size -= 1; }배열의 인덱스는 0부터 시작하므로 마지막 인덱스는 size-1이 된다.
2. 스택 구현 백준 문제 : 스택
1. 일차원 배열를 이용하여 구현
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] stack = new int[n]; int size = 0; while (n-- > 0) { String c = sc.next(); if (c.equals("push")) { int num = Integer.parseInt(sc.next()); stack[size++] = num; } else if (c.equals("top")) { if (size == 0) { System.out.println("-1"); } else { System.out.println(stack[size - 1]); } } else if (c.equals("size")) { System.out.println(size); } else if (c.equals("empty")) { if (size == 0) { System.out.println("1"); } else { System.out.println("0"); } } else if (c.equals("pop")) { if (size == 0) { System.out.println("-1"); } else { System.out.println(stack[size - 1]); size -= 1; } } }2. Stack 라이브러리 사용
- 자바에서 제공하는 Stack 라이브러리를 사용하면 배열로 구현할 필요가 없다.
- 자바API Stack 여기를 참고하면 메소드를 확인할 수 있다.
- 1번과 같은 문제를 Stack 라이브러리를 사용하여 구현함.
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Stack<Integer> stack = new Stack<>(); for(int i=0; i<n; i++) { String c = sc.next(); if(c.equals("push")) { int num = Integer.parseInt(sc.next()); stack.push(num); }else if(c.equals("top")) { if(stack.empty()) { System.out.println("-1"); }else { System.out.println(stack.peek()); } }else if(c.equals("size")) { System.out.println(stack.size()); }else if(c.equals("empty")) { if(stack.empty()) { System.out.println("1"); }else { System.out.println("0"); } }else if (c.equals("pop")) { if(stack.empty()) { System.out.println("-1"); }else { System.out.println(stack.pop()); } } } }
3. 문제
문제 1. 백준 문제 : 단어뒤집기
- 스택의 성질을 이용하여 구현할 수 있다.
- 입력으로 문장이 주어졌을때 공백이나 문자열의 끝을 만나기 전까지 해당 단어의 알파벳을 스택에 넣는다.
- 공백이나 문자열의 끝이면 스택에서 pop 연산을 통해 빼내어 역순으로 만들면 된다.
public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(bf.readLine()); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); while(t-- > 0) { String str = bf.readLine() + "\n"; Stack<Character> s = new Stack<Character>(); for(char ch : str.toCharArray()) { if(ch == '\n' || ch == ' ') { while(!s.isEmpty()) { bw.write(s.pop()); } bw.write(ch); }else { s.push(ch); } } } bw.flush(); }
문제 2. 백준 문제 : 괄호
- 괄호 문자열 ( '(' 와 ')'로만 이루어진 문자열 )이 주어졌을 때, 올바른 괄호 문자열인지 판단하는 문제
- 스택을 이용하여 주어진 괄호 문자열에서 '(' 이면 스택에 push하고 ')'일 경우 스택에서 제일 위에있는 '('와 짝을 맞춘다.
- 정상적으로 수행하였을 때 스택이 비어있어야 한다.
- 모든 과정이 끝났는데, 스택에 '('이 남아있으면 올바르지 못한 괄호 문자열이다.
- 또한 ')'가 남았는데, 스택에 '('이 없다면 이 역시 올바르지 못한 괄호 문자열이다.
코드 1
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { System.out.println(isValid(sc.next())); } } public static String isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(s.charAt(i)); } else { if (!stack.isEmpty()) { stack.pop(); } else { return "NO"; } } } if (stack.isEmpty()) { return "YES"; } else { return "NO"; } }코드 2
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while(n-- > 0) { System.out.println(isValid(sc.next())); } } public static String isValid(String s) { int n = s.length(); int cnt = 0; for(int i = 0; i<n; i++) { if(s.charAt(i) == '(') { cnt += 1; }else { cnt -= 1; } if(cnt < 0) { // 아직 괄호 문자열이 남아있는데 닫는 괄호가 또 왔을 경우 return "NO"; } } if(cnt == 0) { return "YES"; }else { return "NO"; } }코드 2는 스택을 구현하지 않고, 스택의 size만을 이용하여 '('가 몇개가 오는지를 판단하여 구현한 방식이다.
문제 3. 백준 문제 : 스택 수열
- 임의의 수열 A가 있을 때, 스택을 이용하여 이 이 수열을 만들 수 있는지 없는지 구하는 문제이다.
- push하는 순서는 오름차순이다.
- 예를들어 A = [4,3,6,8,7,5,2,1] 이고 첫 인덱스 4는 스택에 1, 2, 3, 4가 들어갈수 있고
- 이때 pop을 하게되면 ++++- 형태가 된다.
- 변수 m은 해당 스택에 추가되어야 하는 수를 의미한다.
- m 이 i번째 수보다 작으면 스택에는 m부터 i번째 수까지 push를 한다.
- m이 i번째 수보다 큰 경우는 불가능한 경우이다.
- m 과 i번째 수와 같은경우 pop을 하면 된다.
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); } result(a); } public static void result(int[] a) { int n = a.length; Stack<Integer> stack = new Stack<Integer>(); int m = 0; StringBuilder sb = new StringBuilder(); for(int x : a) { if(x > m) { while(x > m) { stack.push(++m); sb.append("+\n"); } stack.pop(); sb.append("-\n"); }else { if(stack.peek() != x) { System.out.println("NO"); return; } stack.pop(); sb.append("-\n"); } } System.out.println(sb); }
문제 4. 백준 문제 : 에디터
- 문자열을 이용하여 구현할 수 있지만 시간복잡도 이 된다. 즉, 오래걸린다.
- 두 개의 스택을 만들어 하나는 커서 왼쪽, 다른 하나는 커서 오른쪽으로 하여 문자열을 넣어 구현한다.
- 스택으로 구현하는 경우 pop과 push 연산이 상수시간 즉, 시간복잡도는 이다.
- 문자열로 구현하는 것보다 성능이 좋아진다.
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); Stack<Character> left = new Stack<Character>(); Stack<Character> right = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { left.push(s.charAt(i)); } int m = Integer.parseInt(br.readLine()); while (m-- > 0) { String[] line = br.readLine().split(" "); char what = line[0].charAt(0); if (what == 'L') { if (!left.empty()) { right.push(left.pop()); } } else if (what == 'D') { if (!right.empty()) { left.push(right.pop()); } } else if (what == 'P') { char c = line[1].charAt(0); left.push(c); } else if (what == 'B') { if (!left.empty()) { left.pop(); } } } while (!left.empty()) { right.push(left.pop()); } StringBuilder sb = new StringBuilder(); while (!right.empty()) { sb.append(right.pop()); } System.out.println(sb); }
- 출력할 때는 왼쪽 스택에서 오른쪽 스택으로 push를 먼저 하고, 이후 오른쪽 스택에서 pop을 통해 출력한다.
참고
백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.
