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

짝지어 제거하기 : programmers.co.kr/learn/courses/30/lessons/12973

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

이 문제는 greedy문제였다.

그냥 풀면 된다.

하지만 그냥 그리디로 푼다면 테스트 케이스는 다맞을 순 있겠지만 효율성까지 맞을 순 없다.

따라서 Stack자료구조를 사용 하였다.

import java.util.*;
class Solution
{
public Stack<Integer> stack = new Stack<Integer>();

	public int solution(String s) {

		char[] cArr = s.toCharArray();
		int idx1 = 0, idx2 = 1;

		while (idx2 < s.length()) {
			if (cArr[idx1] == cArr[idx2]) {
				cArr[idx1] = ' ';
				cArr[idx2] = ' ';

				if (stack.isEmpty()) {
					idx2 += 2;
					idx1 = idx2 - 1;
				} else {

					idx1 = stack.pop();
					idx2 = idx2 + 1;
				}
			} else {
				stack.push(idx1);
				idx1 = idx2;
				idx2++;
			}
		}
		if (new String(cArr).trim().isEmpty()) {
			return 1;
		}
		return 0;
	}
}

먼저 인덱스를 두개를 설정하여 비교 한다.

두 인덱스의 문자가 같지 않다면 idx1의 값을 스텍에 넣고 두 인덱스를 한칸씩 전진 한다.

반대로 두 인덱스의 문자가 같다면 해당 자리에 공백 문자를 넣고 스텍이 비어있다면 idx2는 두칸을 전진 하고 idx1은 현재 idx2의 이전칸인 idx2-1위치로 업데이트 시켜준다.

만약 스텍이 비어있지 않다면 idx1은 스텍에서 하나를 빼내어 그 값을 주고 idx2는 한칸을 전진한다.

이번 문제는 어렵진 않았지만 효율성에서 Stack을 떠올리지 못하여 시간을 잡아먹은 케이스이다 ㅠ

그래도 짝을 지을때는 Stack을 사용하면 좋다는 것을 알았으므로 좋은 경험이었다^^