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

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

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스

 

틀린 코드

class Solution
{
    	static int solution(String s){
		StringBuilder sb = new StringBuilder(s);
		while(true) {
			boolean flag = true;
			for(int i=0; i<sb.length()-1; i++) {
				// 같은 알파벳이 2개 붙어있는 짝
				if(sb.charAt(i) == sb.charAt(i+1)) {
					sb.delete(i, i+2);	// i, i+1 문자 제거
					flag = false;
					break;
				}
			}

			// 문자열을 모두 제거했거나, 제거할 문자열이 없을경우 탈출
			if(sb.length() == 0 || flag)
				break;
		}

		if(sb.length() == 0)
			return 1;
		else
			return 0;
	}
}

풀이

문제를 보고 문자열을 제거하기 쉬운 StringBuilder로 변환하고,

모든 문자열을 탐색하며 같은 알파벳이 2개 붙어있는 짝일경우, 제거한다.

만약 문자열을 모두 제거했거나, 아니면 문자열을 탐색하며 제거할 문자가 없는경우 while문을 탈출한다.

문자열의 길이가 0이면 1, 길이가 0이 아니면 0을 리턴했지만 시간초과가 발생했다.

 

 

정답 코드

import java.util.Stack;

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

풀이

 

Stack을 선언하고, 스택에 비어있지 않거나 스택에서 가장 top 값이 현재 비교할 값과 같을경우

pop()을 통해 현재 peek값을 제거하고, 그렇지 않을경우 push()를 통해 현재 값을 넣는다.

 

위 예제 "baabaa" 를 그림으로 그려보면 위와 같다.

먼저 첫번째값 'b' 는 스택이 비어있으므로 push한다.

그 후 a값은 현재 스택의 peek값(b) 와 다르므로 역시 push한다.

그 후 a값은 현재 스택의 peek값(a) 와 같으므로 pop을 통해 a를 제거한다 -> 스택의 현재값은 b

그 후 b값은 현재 스택의 peek값(b)와 같으므로 pop을 통해 b를 제거한다 -> 스택은 현재 비어있는 상태.

그 후 a를 넣고, peek값이 a이므로 pop을 통해 a를 제거한다.

최종적으로 스택은 비어있는 상태가 된다.

 

위 문제를 보고 스택이 바로 떠올랐다면 손쉽게 해결할 수 있었지만, 떠오르지 않아 바로 해결은 못했다.

알고리즘을 풀때 접근방법을 생각하는 것도 좋지만, 무슨 알고리즘인지 생각하고 풀어야겠다 .

위 문제와 동일한 문제

 

백준 3986번 좋은 단어