스택

  • 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

  • 마지막으로 넣은 것이 가장 먼저 나오기 때문에 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를 이용한 문제 해결 아이디어

        • 기존 개수 세기 아이디어에서 발전

        • '(' 여는 괄호가 들어온 경우와 ')' 닫는 괄호가 들어온 경우를 구분하여 조건

          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이기 때문.
          • 실제 구현 소스

            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<Integer> 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한다.
        • 구현

          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)의 시간 복잡도를 갖는다.