[프로그래머스/Java] 12973 짝지어 제거하기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

 

 

🔍  해결 과정

주어진 문자열의 길이의 최대 길이가 100만이므로 직접 문자를 삭제하고 다시 문자의 배열을 수정하면서 문자의 짝을 비교하기에는 비효율적입니다.

 

대신에 스택 자료구조(시간복잡도: O(1))를 활용하여 서로 짝을 이루지 못하는 문자들을 담아둔 다음 나중에 짝을 지을 수 있는지 문자를 비교함으로써 문제를 해결할 수가 있습니다. s의 문자 내용을 살펴보면서 다음과 같은 과정으로 스택을 활용하였습니다.

1️⃣ s에서 보고 있는 현재 인덱스와 그 다음 인덱스의 값이 같지 않다면 스택에 현재 보고 있는 인덱스의 문자를 담는다.
2️⃣ s에서 보고 있는 현재 인덱스와 그 다음 인덱스의 값이 같다면 짝을 이루는 문자의 인덱스는 지나치고, 현재 스택에 있는 문자와 짝을 이루고 있는 문자는 없는지 확인해준다.
3️⃣ s의 문자들을 다 살펴본 후 마지막에 스택에 문자가 존재한다면 짝을 이루는 문자가 아님을 나타낸다.

 

 

---

✏️ 코드

import java.util.*;

class Solution {
    // 각각 짝지어져 있으면 제거하기
    // 이 둘을 합쳐서 비교해보기
    // abcddcba
    // baabaa
    // s의 최대 길이: 100만
    public int solution(String s) {
        int answer = 1;
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        
        for (int i = 0; i < len; ) {
            if (i == len - 1 || i + 1 < len && s.charAt(i) != s.charAt(i + 1)) {
                stack.push(s.charAt(i++));
            } else {
                i += 2;
                
                while (!stack.isEmpty() && i < len && stack.peek() == s.charAt(i)) {
                    stack.pop();
                    ++i;
                }
            }
        }
        
        if (stack.size() > 0) {
            answer = 0;
        }
        
        return answer;
    }
}