프로그래머스 코딩테스트 문제 - [Lv.2] 짝지어 제거하기 (Java)

문제 출처 - 링크

알고리즘 분류

• 스택

📋 문제 요약 설명

• 문자열을 탐색하면서 같은 알파벳이 2개 붙어있는 부분을 찾는다.

• 붙어있는 알파벳 2개를 제거하고, 남은 앞, 뒤 부분을 붙여서 문자열을 만든다.

• 위 과정을 반복하면서 문자열을 모두 제거할 수 있으면 1을 반환, 아니면 0을 반환한다.

💡 알고리즘 설계 / 접근 방법

1. 문자열을 문자로 나누어 스택에 저장되어 있는 값과 비교한다.

2. 저장되어 있는 값과 같다면 그 값을 스택에서 제거한다.

3. 다르다면 스택에 문자를 저장한다.

➕ 보완하기 / 성능 비교

• 처음에는 문자열을 활용해서 풀었고, 정확성 테스트는 통과했지만, 효율성 테스트는 시간초과 했다.

• 시간 복잡도가 O(N²)이 나와서 스택 풀이법으로 바꾸게 되었다.

✅ 풀이

시간 복잡도 → O(N)

• n은 문자열 s의 길이

// 스택 풀이

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == ch) {
                // 이전 문자와 같으면 스택에 저장된 같은 문자 제거
                stack.pop();
            } else {
                // 아니면 넣기
                stack.push(ch);
            }
        }

        // 스택이 비었으면 모든 문자가 제거된 상태
        return stack.isEmpty() ? 1 : 0;
    }
}