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

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12973?language=java

프로그래머스

 

문제 요약

주어진 문자열 s에 대해 짝지어 제거하기가 가능하면 1, 아니면 0 반환하기

• 짝지어 제거하기: 문자열에서 같은 알파벳이 2개 붙어있는 짝을 제거한 뒤, 앞뒤로 문자열을 이어 붙인다. 이를 반복해서 문자열이 모두 제거된다면 성공
• 예시: `baabaa` → `bbaa` → `aa` → 성공

 

제한

• 문자열의 길이 : 1,000,000 이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

풀이

문자열 길이가 10^6으로 알고리즘의 시간복잡도가 O(nlogn) 이하이면 됩니다.

1. 문자열의 첫 부분부터 짝을 찾는다.
   1. 검사한 마지막 부분 + 그 전 부분의 값이 동일하면 짝이다.
2. 짝을 찾으면 이를 제거한다.
3. 제거한 뒷부분부터 다시 검사하여 1~2 과정을 반복한다.

여기서 찾을 수 있는 키워드는 ‘마지막 부분’, ‘제거’, ‘empty’입니다.

이 키워드를 통해 스택을 사용하면 된다는 것을 알 수 있습니다.

즉, 스택에 문자를 하나씩 삽입해 가며 짝을 찾으면 2번 pop 하는 것을 반복하면 됩니다.

 

코드

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

🏷 시간 복잡도

• N: 문자열 s의 길이
• for문: O(N)
• 최종 시간 복잡도: O(N)