짝지어 제거하기_복습

2026.07.14

문제 풀이

1차 실행 오류

---

98.1/100

실패

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (!stack.isEmpty()) {
                while(!stack.isEmpty() && stack.peek() == c) {
                    stack.pop();
                }
            }
            else {
                stack.push(c);
            }
        }
        if (!stack.isEmpty()) {
            return 0;
        }
        return 1;
    }
}

나의 코드

---

실패 원인
비어 있지 않을 때 가장 위쪽에 있는 값을 제거하지 못한다면
큐에 이번 문자를 삽입해야함

---

소요 시간

17분

---

시간 복잡도

$O(n)$

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        boolean removed = false;
        
        for (int i = 0; i < s.length(); i++) {
            removed = false;
            char c = s.charAt(i);
            
            while (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
                removed = true;
            }
            if(!removed) {
                stack.push(c);
            }
        }
        return (stack.isEmpty() ? 1 : 0);
    }
}

AI 코드

---

코드 분석

기존 코드의 while문은 0번 또는 1번 실행되므로 if 문으로 변경하였음

Deque를 사용하지 않아
메모리 지역성과 객체 생성과 Character 오토 박싱/언박싱 오버헤드 제거

---

시간 복잡도

$O(n)$

---

class Solution {
    public int solution(String s) {
        char[] stack = new char[s.length()];
        int top = -1; // 스택 포인터

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (top >= 0 && stack[top] == c) {
                top--; // 짝 제거
            } else {
                stack[++top] = c;
            }
        }
        return (top == -1) ? 1 : 0;
    }
}