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

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

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

주어진 문자열에서 2개 쌍이 되는 문자를 전부 제거하는 문제이다.

처음에 StringBuilder를 이용해서 특정 인덱스를 뽑아내는 방식으로 했었는데 효율성에서 통과를 못했다.

그래서 Stack이라는 자료구조를 이용해서 좀 더 개선했다.

문자를 하나씩 넣어서 비교를 하고 제거해가는 방식이다!

 public int solution(String s)
    {
        Stack<Character> space = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            Character ca = s.charAt(i);
            if(space.size() > 0 && space.peek() == ca) {
                space.pop();
            } else {
                space.push(ca);
            }
        }

        return space.size() == 0 ? 1 : 0;
    }

 

테스트 케이스

import org.junit.Assert;
import org.junit.Test;

public class 짝지어_제거하기Test {
    @Test
    public void test1() {
        // when
        String s = "baabaa";

        // given
        짝지어_제거하기 so1 = new 짝지어_제거하기();
        int result = so1.solution(s);

        // then
        Assert.assertEquals(1, result);
    }
    @Test
    public void test2() {
        // when
        String s = "cdcd";

        // given
        짝지어_제거하기 so1 = new 짝지어_제거하기();
        int result = so1.solution(s);

        // then
        Assert.assertEquals(0, result);
    }
    @Test
    public void test3() {
        // when
        String s = "acdaadca";

        // given
        짝지어_제거하기 so1 = new 짝지어_제거하기();
        int result = so1.solution(s);

        // then
        Assert.assertEquals(1, result);
    }
}

 

 

 

최초에 풀었던 방법...(인덱스를 어떻게 다시 순환할까 하다가 -1로 했다... 정확성은 맞지만 매우 무식하게...)

class Solution
{
    public int solution(String s)
    {
         StringBuilder sb = new StringBuilder(s);

        for(int i = 0; i < sb.length() - 1; i++) {
            char target = sb.charAt(i);
            if(target == sb.charAt(i + 1)) {
                sb.deleteCharAt(i+1);
                sb.deleteCharAt(i);
                i = -1;
                continue;
            }
            if(i != 0 && target == sb.charAt(i - 1)) {
                sb.deleteCharAt(i);
                sb.deleteCharAt(i-1);
                i = -1;
                continue;
            }

        }
        return sb.length() == 0 ? 1 : 0;
    }
}