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

programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

문제풀이

일단 문자열의 길이가 1,000,000이하의 자연수 이기때문에 O(N^2)으로 풀게 된다면 시간초과가 난다.

문자열에서 같은 알파벳이 2개 붙어 있는 짝은 바로바로 제거 시켜줍니다. 이어 붙이는 작업을 할 필요가 없다.

문제 자체에서 다 제거가 가능하냐 불가능 하냐만 체크하기 때문이다. 올바른 괄호 찾기 문제와 매우 유사합니다.

Stack을 사용하면 위 같은 문제를 확인이 가능하다. 검사하는 문자와 맨 위에 문자가 같다면 pop() 해주고

같지 않다면 push()하여 stack에서 관리해준다. 문자열 끝까지 검사를 하였을때 Stack에 사이즈가 0이면 짝을 다 이루었음으로 answer = 1 이다.

코드

import java.util.*;

class Solution
{

	public int solution(String s) {
		int answer = 0;
		
		Stack<Character> st = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(st.isEmpty()){
                st.push(s.charAt(i));
            }
            else{
                if(s.charAt(i) == st.peek()) st.pop();
                else st.push(s.charAt(i));
            }
        }
		
        if(st.size() == 0) answer = 1;
        
		return answer;
	}
}