[프로그래머스 JAVA] 짝지어 제거하기

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

 

1. 문제 요약

• 알파벳 소문자로 이루어진 문자열에 같은 문자열이 2개 붙어있다면 제거한다
• 위 과정을 반복해서 문자열을 모두 제거할 수 있다면 1, 아니라면 0을 리턴한다.
• 문자열의 길이는 1,000,000 (백만) 이하의 자연수

 

 

2. 내가 막혔던 지점

• 처음에는 큐나 스택과 같은 자료구조를 사용하면
  문자열 길이가 최대 백만이기 때문에 메모리가 많이 들 것 같다는 걱정이 들었다.
• 그래서 반복문으로 문자열을 순회하면서
  연속된 문자가 발견되면 substring을 이용해 직접 문자열을 이어 붙이는 방식으로 구현했다.

s = s.substring(0, i - 1) + s.substring(i + 1);

• 논리적으로는 맞는 풀이였지만,
  • 문자열을 매번 새로 생성해야 했고
  • 최악의 경우 문자열 길이만큼 substring이 반복되면서
  결국 시간 초과가 발생했다.

 

3. 핵심 아이디어

• 이 문제의 핵심은 “바로 이전 문자와 현재 문자를 비교하는 것”이다.이를 위해 스택을 사용했다.
  • 스택이 비어 있지 않고
  • 현재 문자와 스택의 peek() 값이 같다면 → 짝이므로 pop
  • 다르다면 → 현재 문자를 push
  이 과정을 문자열 끝까지 반복한다. 최종적으로 스택이 비어 있으므로 모든 문자를 제거할 수 있다..
• 예를 들어 baabaa를 처리하면:
• 모든 문자를 저장해 두었다가 한 번에 처리할 필요는 없고,
  문자열을 왼쪽부터 하나씩 보면서 직전 문자와만 비교하면 된다.

4. 실수 포인트

• substring은 단순히 문자열을 자르는 연산처럼 보이지만,
  실제로는 새로운 문자열을 생성하는 비용이 큰 연산이다.
• 문자열 길이가 크고, 이 연산이 반복되면
  시간 복잡도가 급격히 증가할 수 있다는 점을 미리 알고 있었다면
  불필요한 시행착오를 줄일 수 있었을 것 같다.

5. 코드

import java.util.*;
class Solution
{
    
    public int solution(String s) {
        Stack<Character> st = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            
            if(st.isEmpty() || st.peek() != cur) {
                st.push(cur);
            } else {
                st.pop();
            }
        }
        
        return st.isEmpty() ? 1 : 0;
    }
}