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

문제

프로그래머스-짝지어 제거하기

주어진 문자열에서 같은 알파벳이 2개 붙어있는 짝을 찾아 제거하며 전체 문자열을 제거할 수 있는지 판단하는 문제.

• 예시
  baabcc가 주어졌을 때
  baabcc -> bbcc -> cc ->
  모든 문자열을 제거할 수 있으므로 1을 리턴한다
  모든 문자열을 제거할 수 없는 경우 0을 리턴한다

풀이

• 제한 사항
  문자열의 길이 : 1,000,000 이하의 자연수
  문자열은 모두 소문자로 이루어져 있다

1. 문자열의 길이가 짝수면 진행하고, 홀수면 0을 리턴한다(진행할 필요 x)
   문자열의 앞부터 1글자씩 반복하며 스택에 넣는다
2. 스택의 크기가 0인경우 스택에 넣는다
3. 스택의 크기가 0이 아닌 경우, 가장 최상단(최근에 삽입한 값)과 비교하여 같으면 최상단 값을 제거한다
   다른 경우, 스택에 넣는다
4. 반복이 끝난 후 스택의 크기가 0이면 모든 문자열을 제거했으므로 1을 리턴한다
   0이 아닌경우 남아있는 글자가 있다는 뜻이므로 0을 리턴한다

시행착오(시간초과)

문자열의 길이가 큰 만큼 반복하는 횟수를 줄이지않으면 시간이 터지게 되어있다
처음 구상했을 때 left, right의 인덱스를 둬서 각각에 해당하는 글자가 같으면 삭제처리를 하고
left는 왼쪽으로, right는 오른쪽으로 이동 후 이어나가는 방식으로 구현했다
left가 0에 도달하거나 더이상 왼쪽에 글자가 남아있지 않으면
left는 right로 이동하고 right는 다음 유효한 우측 글자로 넘겨 비교/삭제를 이어나갔다
하지만 left, right를 선정하는 방법에서 유효한 글자를 찾기까지 반복문을 돌면서 효율성테스트3~8을 통과하지 못했다 ㅠㅠ

소스코드

import java.util.*;
class Solution{
	public int solution(String s) {
	if (s.length() % 2 != 0)
			return 0;
		Stack<Character> str = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if(str.size()==0) {
				str.add(s.charAt(i));
			}else {
				char top = str.peek();
				if(top == s.charAt(i)) {
					str.pop();
				}else {
					str.add(s.charAt(i));
				}
			}
		}
		return str.size()==0 ? 1 : 0;
	}
}