[220717][Tany][인프런](5-5) 쇠막대기

[juni8453]

📌 문제

• 문제

⭐️ 아이디어

• 괄호 문자열을 탐색해서 쇠막대기인지 레이저인지 구분하는 문제이기 때문에 Stack 자료구조를 사용해서 풀이.
• 열린 괄호인 경우 Stack 에 값을 push() 해주다가 닫힌 괄호가 나왔을 때 쇠막대기인지 레이저인지 구별하면 될 것 같다.

🤔 고민한 내용

• 최초 푼 방식으로는 예제 1번 빼고 다 틀렸다 .. ㅠㅠ
• stack.peek() 메서드를 활용해 닫힌 괄호일 때, 앞선 괄호가 열린 괄호인지 (-> 레이저), 닫힌 괄호인지 (-> 쇠막대기) 판단해서 풀이했는데, 이렇게 하면 레이저인 경우의 if 문은 타지만 쇠막대기인 경우의 if 문을 타지 않는 문제가 발생했다.
• 아마도 닫힌 괄호가 나왔을 때 Stack 의 맨 위 값은 무조건 열린 괄호이기 때문에 그런 듯.
• 그래서 stack.peek() 를 사용해서 풀지 않고, Input 문자열의 인덱스에서 괄호를 판단하는 방식으로 풀이를 바꿨다.

💪 새롭게 배운 내용

• 문제 설명이 길고 복잡했지만 생각보다 간단한 문제였고, 역시 괄호 관련 문제는 Stack 을 고려하는 ? 템플릿이 머리 속에 어느정도 잡힌 것 같다.

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

✅ 본인 풀이

🏋️‍♀️ 시도횟수 : 2회 | ⏱ 걸린시간 : 123ms | 💾 메모리 : 26MB

1. 최초 풀이 방식 (오답)

   
   import java.io.IOException;
   import java.io.BufferedReader;
   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)); String input = br.readLine();

    int answer = solution(input);
    System.out.println(answer);
}

private static int solution(String input) {
    int count = 0;
    Stack<Character> stack = new Stack<>();

    for (char x : input.toCharArray()) {
        // 열린 괄호일 때,
        if (x == '(') {
            stack.push(x);

        // 닫힌 괄호일 때, peek() 이 열린 괄호인지 아닌지 판단.
        } else {
            if (stack.peek() == '(') {
                // 닫힌 괄호 바로 앞이 열린 괄호이므로 레이저.
                // Stack 에 들어있는 열린 괄호 갯수만큼 쇠 막대기가 존재하기 때문에 레이저를 만나면 해당 열린 괄호 갯수만큼 더해야 한다.
                // 더하기 전에 레이저의 열린 괄호는 Stack 에서 지워주자.
                stack.pop();
                count += stack.size();

            } else {
                // 닫힌 괄호 바로 앞이 열린 괄호가 아니므로 레이저가 이닌 쇠 막대기.
                stack.pop();
                count ++;
            }
        }
    }

    return count;
}

}

2. 두번째 풀이 방식 (정답)
~~~java
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Section0504 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int answer = solution(input);
        System.out.println(answer);
    }

    private static int solution(String input) {
        int count = 0;
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(') {
                stack.push(input.charAt(i));
            } else {
                // 레이저라면 ?
                if (input.charAt(i - 1) == '(') {
                    stack.pop();
                    count += stack.size();
                // 쇠 막대기라면 ?
                } else {
                    stack.pop();
                    count ++;
                }
            }
        }

        return count;
    }
}

참고한 자료

• 링크