[프로그래머스(programmers)] (2017 팁스타운) 짝지어 제거하기

알고리즘 문제 풀이 / 프로그래머스 (programmers)  -  짝지어 제거하기

 

 

문제 링크

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

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

 

 

문제 풀이

 

stack 과 substring() 을 사용해서 푼다.

 

이 문제를 보자마자 처음 든 생각은 앞에서부터 문자를 추출해와서 다음 단어와 같으면 replace로 지워주고 다시 처음부터 반복하는 알고리즘을 떠올렸다. 그랬더니 반정도는 시간초과에 효율성은 전부 시간초과였다. For문을 한 번 썼다고, 혹은 코드가 짧다고 효율적인 코드가 아니란 것을 다시금 생각하게 되었다. 그리고 나서 다시 문제를 생각해보는데 결국 대칭적 구조여야한다는 생각이 들었다. 그래서 stack을 사용하여 문자를 앞에서 부터 하나씩 쌓아 올렸고, 스택 top 부분과 새로 가져온 글자가 같으면 없애는 방법으로 하니 아주 빠르게 잘 돌아갔다. 

 

처음시도 (시간 초과)

public static int solution(String s){
	int answer = 0;
	for(int i = 0; i < s.length() - 1 ; i++ ) {
       	String str = s.substring(i, i+1);
       	if(str.equals(s.substring(i+1, i+2))) {
       		s = s.replaceFirst(str + str, "");
       		i = -1;
       		if(s.length() == 0) {
       			answer = 1;
       			break;
       		}
       	}
    }
	return answer;
}

 

 

두번째 시도 (성공)

public static int solution(String s){
	int answer = 0;
	Stack<String> stack = new Stack<>();

	stack.push(s.substring(0 , 1));
	for(int i = 1; i < s.length(); i++ ) {
		if(stack.size() != 0 && s.substring(i, i+1).equals(stack.peek())) {
			stack.pop();
		}else {
			stack.push(s.substring(i ,i+ 1));
		}

	}
	if(stack.size() ==0) {
		answer = 1;
	}
	return answer;
}