[프로그래머스/Java] Lv.2 - 짝지어 제거하기

📝 문제 설명

알파벳 소문자로 이루어진 문자열을 대상으로, 같은 알파벳이 2개 붙어 있는 '짝'을 찾아 제거합니다. 제거된 후 앞뒤로 문자열을 이어 붙이는 과정을 반복하여, 문자열을 모두 제거할 수 있는지 확인하는 문제입니다. 성공하면 1, 아니면 0을 반환해야 합니다.

• 제한 사항: 문자열의 길이 $1,000,000$ 이하의 자연수.

---

💡 접근 방식

1. 시간 복잡도 고려 ($O(N)$의 필요성)

처음 문제를 보면 "문자열을 직접 지우고 다시 합쳐야 하나?"라는 생각이 들 수 있습니다. 하지만 문자열의 길이가 최대 1,000,000이기 때문에, 매번 문자열을 새로 생성하거나 이중 반복문($O(N^2)$)을 사용하면 무조건 시간 초과가 발생합니다. 따라서 단 한 번의 순회($O(N)$)로 해결해야 합니다.

2. 스택(Stack) 활용

인접한 문자를 비교하고 제거하는 구조는 스택(LIFO) 자료구조에 최적화되어 있습니다.

1. 문자열을 한 글자씩 순회합니다.
2. 스택이 비어 있지 않고, 현재 문자가 스택의 peek()(맨 위)에 있는 문자와 같다면?
   • 짝이 맞으므로 스택에서 pop()하여 제거합니다.
3. 그 외의 경우(스택이 비었거나 문자가 다를 때)는?
   • 스택에 현재 문자를 push()합니다.
4. 모든 순회가 끝난 후 스택이 비어 있다면 모든 짝이 제거된 것이므로 1을, 데이터가 남아 있다면 0을 반환합니다.

---

💻 구현 코드 (Java)

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;

        Stack<Character> st = new Stack<>();
        st.push(s.charAt(0));
        
        for(int i=1; i<s.length(); i++) {
            if(!st.isEmpty() && s.charAt(i) == st.peek()) {
                st.pop();
            }
            else {
                st.push(s.charAt(i));
            }
        }

        if(st.size() == 0) {
            answer = 1;
        }
        
        return answer;
    }
}

✨ 느낀 점

• 제한 사항의 힌트: 입력 데이터가 100만 개라는 조건은 "이중 반복문을 쓰지 마시오"라는 강력한 경고였습니다. 효율성 테스트가 포함된 문제에서는 반드시 시간 복잡도를 먼저 계산해야 함을 다시 체감했습니다.

• 자료구조의 힘: 단순히 String이나 StringBuilder를 조작했다면 코드가 복잡해지고 속도도 느렸을 텐데, 스택을 활용하니 코드가 훨씬 직관적이고 빨라졌습니다.

• 추가 개선점: 자바의 Stack 클래스는 내부적으로 동기화(synchronized) 처리가 되어 있어 약간 느릴 수 있다고 합니다. 다음에는 더 빠른 ArrayDeque를 사용하거나, 배열을 직접 스택처럼 활용하는 최적화 방법도 적용해보고 싶습니다.