스택
-
한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
-
마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다.
-
push: 스택의 가장 위에 자료를 넣는 연산
-
pop: 스택의 가장 위의 자료를 빼는 연산
-
top: 스택의 가장 위의 자료를 보는 연산
-
empty: 스택이 비어있는지 아닌지를 알아보는 연산
-
size: 스택에 저장되어 있는 자료의 개수를 알아보는 연산
-
스택의 구현
- 배열을 이용하여 구현
- push의 구현
- stack의 size번째의 배열에 값을 넣고 size를 1 증가시키면 된다.
- pop의 구현
- stack의 size-1번째를 지워버리고 size를 -1하는 것 -
스택의 예제 1
- boj.kr/9012
- 올바른 괄호 문자열인지 알아보는 문제
- 괄호문자열이란?
- (와 )로만 이루어진 문자열
- 올바른 괄호 문자열: 괄호의 쌍이 올바른 문자열
- 닫는 괄호의 위치는 어디에 위치해야 할까?
- 왼쪽에 있어야 한다.
- 아직 짝이 맞지 않아야 한다.
- 가장 오른쪽에 있는 괄호.
- 가장 빠르게 떠오른 아이디어
- 닫는 괄호의 개수와 여는 괄호의 개수를 세어서 맞으면 클리어?
- )( 등의 문제를 해결할 수 없다.
- 스택에 괄호를 순서대로 PUSH하고 괄호가 맞아떨어지면 POP
- 마지막에 닫는 괄호가 나왔는데 스택이 비어있다면 여는 괄호가 부족
- 마지막에 여는 괄호가 나왔는데 스택이 비어있다면 닫는 괄호가 부족
- 마지막에 스택에 아무것도 남지 않는다면 클리어
- CNT를 이용한 문제 해결 아이디어
- 기존 개수 세기 아이디어에서 발전
- '(' 여는 괄호가 들어온 경우와 ')' 닫는 괄호가 들어온 경우를 구분하여 조건```java public class Main{ String valid(String s) { int cnt = 0; for(int i=0; i<s.length(); i++{ if(s.charAt(i) == '('){ cnt += 1; } else{ if(cnt == 0){ return -1; } else{ cnt -= 1; } } } return cnt; } public static void main(String args[]){ BufferedReader br = new BufferedReader(new InputStreamReader(System.io)); String str = br.readLine(); if(valid(str) == 0) System.out.println("success"); else System.out.println("fail"); } } ``` -
스택의 예제 2
- 쇠막대기 boj.kr/10799
- 쇠막대기 문제 조건
1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'로 표기 모든 '()'는 반드시 레이저를 표기
2. 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.
- PS 아이디어
1. 괄호를 받으며 위치를 인덱스로 기록하며 쇠막대인지 레이저인지 판단
- 열린 괄호를 만날 때 index를 기록
- 닫히는 괄호를 만나면 pop
- pop되는 순간 자신이 레이저인지 쇠막대인지 구분한다.
- index의 차이가 1이라면 레이저
- 아니라면 쇠막대
2. 쇠막대를 지나가는지 판단
- 쇠막대 길이를 저장하는 배열을 만들고 레이저가 그 범위 안이라면 쇠막대는 2조각으로 잘린다.
3. 초기값
- 일단 쇠막대가 하나도 잘리지 않더라도 쇠막대는 그 갯수만큼 조각 수를 갖는다.
- PS 정석 아이디어
- 레이저가 발생하는 경우
- Stack에 아무것도 없는데 레이저가 발생하는 경우
- 아무런 영향을 미치지 못한다.
- Stack에 무언가가 들어있을 때 레이저가 발생하는 경우
- size만큼 piece를 더해주게 된다.
- 그 이유는 괄호가 언젠간 닫히는 것이 보장되어 있기 때문
- 쇠막대기가 발생하는 경우
- piece에 1을 더해준다.
- 쇠막대기 자체도 piece이기 때문.
- 실제 구현 소스```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main{public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack stack = new Stack();
char[] parentheses = br.readLine().toCharArray();int pieces = 0; for(int i=0; i<parentheses.length; i++){ if(parentheses[i] == '('){ stack.push(i); } else { int index = stack.pop(); if(index == i-1){ // 레이저는 빼주고 if(!stack.isEmpty()){ pieces += stack.size(); } } else { pieces++; } } } System.out.println(pieces);}
}``` -
스택의 예제 3
- '에디터' boj.kr/1406
- 조건
- 커서: 문장의 맨 앞, 맨 뒤, 문장 중간 임의의 곳에 위치 가능
- L : 커서를 왼쪽으로 한 칸 옮김
- D : 커서를 오른쪽으로 한 칸 옮김
- B : 커서 왼쪽에 있는 문자를 삭제함
- P $ : $라는 문자를 커서 오른쪽에 추가함. 커서는 $에 위치
- 입력받은 명령어를 수행한 뒤의 문자를 출력하면 된다.
- 문제의 N제한이 중요하다.
- 길이가 10만을 넘지 않는다.
- 명령어의 갯수는 60만을 넘지 않는다.
- 아이디어 1
- LinkedList< Char>를 이용하여 풀기
- ArrayList vs LinkedList의 상황에서 LinkedList는 Add Remove가 O(1)의 시간이어서 선택
1. LinkedList에 문자열을 한자씩 넣어놓는다.
2. 커서의 위치는 index라는 변수에 저장
- index는 0이하로 줄지 않는다.
- index는 ArrayList의 길이보다 커지지 않는다.
3. B(DELETE)명령어는 index번째에 있던 문자를 지운다.
4. P $는 index번째에 문자를 추가시킨다.
- 구현
- A```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; public class Main{ public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); LinkedList<Character> chList = new LinkedList<>(); char[] chars = br.readLine().toCharArray(); int index; for(index=0; index<chars.length; index++){ chList.add(chars[index]); } int n = Integer.parseInt(br.readLine()); for(int i=0; i<n; i++){ String op = br.readLine(); // P if(op.length() > 1){ chList.add(index, op.toCharArray()[2]); index++; } else if(op.equals("L")){ if(index > 0) index--; } else if(op.equals("D")){ if(index < chList.size()) index++; } // B else { if(!chList.isEmpty() && index > 0) chList.remove(--index); } } StringBuilder sb = new StringBuilder(); for( char c : chList ){ sb.append(c); } System.out.println(sb.toString()); } } ``` > 이 방법은 시간을 초과한다. O(n)의 연산속도 때문.. - 아이디어 2 - 스택을 이용한 구현 1. 스택 2개 생성 Left and Right Stack 2. 먼저 입력받은 문자열을 Left Stack에 넣는다. 3. L 명령은 Left 스택이 비어있지 않은 경우에 pop하여 Right 스택으로 옮긴다. 4. D 명령은 Right 스택이 비어있지 않은 경우에 pop하여 Left 스택으로 옮긴다. 5. B 명령은 Left Stack을 pop한다. 6. P $ 명령은 Left Stack에 Push한다. - 구현 ```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main{ public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] chars = br.readLine().toCharArray(); Stack<Character> left = new Stack<>(); Stack<Character> right = new Stack<>(); for(int i=0; i<chars.length; i++){ left.push(chars[i]); } int n = Integer.parseInt(br.readLine()); for(int i=0; i<n; i++) { String op = br.readLine(); if(op.length() > 1) // P left.push(op.toCharArray()[2]); else if(!left.isEmpty() && op.equals("L")) right.push(left.pop()); else if(!left.isEmpty() && op.equals("B")) // B left.pop(); else if(!right.isEmpty() && op.equals("D")) left.push(right.pop()); } while(!left.isEmpty()) right.push(left.pop()); StringBuilder sb = new StringBuilder(); while(!right.isEmpty()) sb.append(right.pop()); System.out.println(sb.toString()); } } ``` > 이 방법은 시간을 초과하지 않는다.
스택의 활용
- 스택은 가장 가까운 자료만 의미를 가질 때, 사용하면 좋다.
- 가장 가까운 자료의 삽입, 삭제가 O(1)의 시간 복잡도를 갖는다.
