Stack

💥 실전 예제 1: 괄호 검사

❓ 문제

괄호가 올바르게 닫혔는지 확인하자!

예: "(()())" → O

예: "(()" → X

예: ")(" → X

🧠 핵심 아이디어

여는 괄호 ( → 스택에 push
닫는 괄호 ) → 스택에서 pop
중간에 pop할 게 없거나, 마지막에 스택이 남으면 → 실패

풀었다

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();

        Stack<Character> stack = new Stack<>();

        boolean isMatch = true;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    isMatch = false;
                    break;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) {
            isMatch = false;
        }

        System.out.println(isMatch);
    }
}

🎯 문제: 올바른 괄호 문자열인가?

문자열이 아래 규칙을 모두 만족하면 true, 아니면 false를 출력해줘.

✅ 조건:

괄호는 (), {}, [] 세 종류가 있다.
여는 괄호는 반드시 같은 종류의 닫는 괄호와 짝지어져야 한다.
괄호는 올바르게 중첩되어야 한다.

풀었다

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        System.out.println(isValid(str));
    }

    // 괄호는 (), {}, [] 세 종류가 있다
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char stackChar = stack.pop();
                if (c == ')' && stackChar != '(') {
                    return false;
                } else if (c == ']' && stackChar != '[') {
                    return false;
                } else if (c == '}' && stackChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

🔥 문제 1: 폭발 문자열 (“문자열 폭파기”)

✨ 문제 설명

문자열 S가 주어지고, 폭발 문자열 BOMB이 주어진다.

S에서 BOMB가 나타날 때마다 제거한다. 이걸 반복해서 폭발이 더 이상 일어나지 않을 때까지 처리한 후 남은 문자열을 출력하라.

단,

스택을 이용해서 풀 것!

💡 예시

입력:
S = "mababcababc"
BOMB = "abc"

출력:
"mabab"

💬 조건

문자열 길이 최대 100만
폭발 문자열 길이 최대 36
시간 초과 방지를 위해 StringBuilder + Stack 구조 사용

풀기 (답지를 봤다.)

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.next();
        String bomb = sc.next();
        System.out.println(bombB(s, bomb));
    }

    public static String bombB(String s, String bomb) {
        StringBuilder result = new StringBuilder();

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            stack.push(c);

            if (stack.size() >= bomb.length()) {
                boolean isMatch = true;
                for (int i = 0; i < bomb.length(); i++) {
                    if (stack.get(stack.size() - bomb.length() + i) != bomb.charAt(i)) {
                        isMatch = false;
                        break;
                    }
                }

                if (isMatch) {
                    for (int i = 0; i < bomb.length(); i++) {
                        stack.pop();
                    }
                }
            }
        }

        for (char c : stack) {
            result.append(c);
        }

        return result.toString();
    }
}

패착
- GPT 가 답을 이상하게 줬다 → mabab 인데 자꾸 mab 이라 해서 내가 잘못 생각한 줄 → 그래서 꼬였음
- stack.get() 을 몰라서 인덱스로 비교할 수 있는지 몰랐다..
  - 다음엔 활용하면 좋을 것

✍ 문제 2: 좋은 문자열

✨ 문제 설명

문자열 s가 주어졌을 때, 연속으로 같은 문자가 두 번 나오면 제거한다.

이걸 반복해서 문자열이 비거나 더 이상 없을 때까지 처리하고 남은 문자열을 출력하라.

역시

스택

💡 예시

입력: "aabccba"
과정: "aabccba" → "bccba" → "bba" -> "a"
출력: "a"

문제풀기

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.next();
        System.out.println(str(s));
    }

    public static String str(String s) {
        StringBuilder result = new StringBuilder();

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        for (char c : stack) {
            result.append(c);
        }

        return result.toString();
    }
}

설명

        
        for (char c : s.toCharArray()) {
		        // 스택이 비어있지 않고, 스택의 앞문자열이 c와 같으면 앞문자열도 pop
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
            // 스택이 비어있거나, 스택의 앞 문자열이 c와 다르면?!
                stack.push(c);
            }
        }

728x90