📌 서론.

이번 강의는 스택의 응용이기에 따로 강의 블로깅은 만들지 않았다 대신 문제를 풀려고 한다.

📚 오늘의 문제.

📝 문제 0. 괄호

링크 : https://www.acmicpc.net/problem/9012

1. 문제 설명

   

2. 문제 풀이

   전체적인 과정은 바킹독에 있던 알고리즘과 동일하다.

   여는 괄호가 나오면 계속해서 스택에 추가하고 닫는 괄호가 나왔을 경우,

   → 스택이 비어있으면 올바르지 않은 괄호 쌍

   → 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍

   스택의 top 이 짝이 맞는 괄호일 경우 pop

   모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호쌍. 남아있지 않으면 올바른 괄호쌍.

   //괄호 9012
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.HashMap;
   import java.util.Stack;
   
   class Main {
   
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();
   
       int tc = Integer.parseInt(br.readLine());
       for (int i = 0; i < tc; i++) {
         String line = br.readLine();
         if (isBalanced(line)) {
           sb.append("YES\n");
         } else {
           sb.append("NO\n");
         }
       }
   
       System.out.print(sb.toString());
       br.close();
     }
   
     private static boolean isBalanced(String line) {
       Stack<Character> bracketStack = new Stack<>();
       HashMap<Character, Character> bracketDict = new HashMap<>();
       bracketDict.put('(', ')');
   
       for (char c : line.toCharArray()) {
         if (c == '(') {
           bracketStack.push(c);
         } else if (c == ')') {
           if (bracketStack.isEmpty()) {
             return false;
           }
           char openBracket = bracketStack.pop();
           if (bracketDict.get(openBracket) != c) {
             return false;
           }
         }
       }
       return bracketStack.isEmpty();
     }
   }

📝 문제 1. 좋은 단어

링크 : https://www.acmicpc.net/problem/3986

1. 문제 설명

   

2. 문제 풀이

   해당 문제가 앞선 괄호 스택 문제와 다른 점은 스택의 닫는 괄호와 여는 괄호가 같은 문자로 되어있다는 것이다.

   처음 생각난것은 짝수이면서 뒤집었을 때 같은 대칭 문자열이면 해당 방식을 만족한다는 것이다.

   하지만 해당 방식은 ABBABB 와 같은 예제에 적용할 수 없다.

   두번째로 생각난건 뭔가 뿌요뿌요같다는 생각이 들었다.

   같은 문자를 만났을 때 터지는. 그래서 동일한 문자가 연속으로 나타날 때 스택에 제거하는 방식으로 구현했다.

   1. 만약 스택에 아무것도 없고 ‘A’나 ‘B’가 나왔을 경우 스택에 추가.
   2. 스택에 쌓아가다가 stack.peek() == 현재 문자 일 경우 pop
   3. 모든 문자열을 쌓았는데도 문자가 남아있다면 false.

   // 좋은 단어 3986
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.Stack;
   
   class Main {
   
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
       //input
       int tc = Integer.parseInt(br.readLine());
       int count = 0;
   
       for (int i = 0; i < tc; i++) {
         char[] words = br.readLine().toCharArray();
         if (checkGoodWords(words)) {
           count += 1;
         }
       }
       System.out.println(count);
   
       br.close();
     }
   
     private static Boolean checkGoodWords(char[] words) {
       Stack<Character> stack = new Stack<Character>();
       for (int i = 0; i < words.length; i++) {
         if (stack.isEmpty()) {
           stack.push(words[i]);
         } else if (stack.peek() == words[i]) {
           stack.pop();
         } else{
           stack.push(words[i]);
         }
       }
       return stack.isEmpty();
     }
   }

   if-else를 조금 더 좋게 구현했다.

   // 좋은 단어 3986
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.Stack;
   
   class Main {
   
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
           // input
           int tc = Integer.parseInt(br.readLine());
           int count = 0;
   
           for (int i = 0; i < tc; i++) {
               String word = br.readLine();
               if (checkGoodWords(word)) {
                   count += 1;
               }
           }
           System.out.println(count);
   
           br.close();
       }
   
       private static Boolean checkGoodWords(String word) {
           Stack<Character> stack = new Stack<>();
           for (char c : word.toCharArray()) {
               if (!stack.isEmpty() && stack.peek() == c) {
                   stack.pop();
               } else {
                   stack.push(c);
               }
           }
           return stack.isEmpty();
       }
   }
   

📝 문제 2. 쇠막대기

링크 : https://www.acmicpc.net/problem/10799

1. 문제 설명

   

2. 문제 풀이

   해당 문제는 괄호 문제에 개수를 체크하는 싱크빅한 문제이다.

   보통의 괄호문제에서 스택이 pop되는 시점에 있는 열린 괄호의 개수가 잘려진 쇠막대기의 개수가 된다는 사실을 알게됐다면 당신은 해당 문제를 쉽게 풀 수 있었을 것이다.

   // 쇠막대기 10799
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.Stack;
   
   class Main {
   
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
       //input
       char[] barAndRazor = br.readLine().toCharArray();
       int count = 0;
       Stack<Character> stack = new Stack<Character>();
       for (int i = 0; i < barAndRazor.length; i++) {
         if (barAndRazor[i] == '(') {
           stack.push(barAndRazor[i]);
         } else if (barAndRazor[i] == ')') {
           stack.pop();
           count += stack.size();
         }
       }
   
       System.out.println(count);
       br.close();
     }
   }

   하지만 해당 문제는 두번째 테스트 케이스를 통과하지 못한다.

   사실 항상 스택크기만큼 더하면 안된다. 쇠막대기의 끝부분과 진짜 레이저를 구분해야하기 때문이다.

   예를 들어 해당 TC를 통과하지 못한다.

   ((()()))
   	| |	
    ------
   --------

   해당 테스트 케이스에서 정답은 6이지만 코드는 5로 답한다. 이유는 레이저 부분이 사라지면서 더해진 숫자들은 문제가 되지 않지만, 남아있는 쇠막대기 끝부분도 레이저로 인식하기 때문이다.

   그렇기에 진짜 레이저일 경우에만 stack의 크기만큼을 더해주고 나머지 경우에는 +1 을 해줘야한다.

   // 쇠막대기 10799
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.Stack;
   
   class Main {
   
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
       //input
       char[] barAndRazor = br.readLine().toCharArray();
       int count = 0;
       Stack<Character> stack = new Stack<Character>();
       for (int i = 0; i < barAndRazor.length; i++) {
         if (barAndRazor[i] == '(') {
           stack.push(barAndRazor[i]);
         } else if (barAndRazor[i] == ')') {
           if (barAndRazor[i - 1] == '(') {
             stack.pop();
             count += stack.size();
           } else {
             stack.pop();
             count += 1;
           }
         }
       }
   
       System.out.println(count);
       br.close();
     }
   }

   놀랍게도 해당 문제를 파이썬으로 이전에 풀었었는데 똑같이 틀렸고 똑같이 맞았다…