DS : Stack "baabaa"

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

프로그래머스

 

정확도를 푸는 것은 어렵지 않다.

 

그러나 다음과 같은 코드를 작성을 하는데 있어  디버깅을 사용함에도 효율적이지 못한 코드가 나온다.

1 차적으로 중복이 존재하는 지 탐색을 하는데  

public int solution(String s) {
    int answer = 0 ;

    while (s.length() != 0 ) {
        int check = s.length();
        if(s.length() == 1) return answer ;
        char tmp  =  s.charAt(0);
        int range = s.length();
        for(int i = 1 ; i < range ;i++) {
            if(tmp == s.charAt(i)){
                s = s.substring(0,i-1) +s.substring(i+1);
                range = range -2 ;
                i = i-1;
                tmp = 'A';
            }else{
                tmp = s.charAt(i);
            }

        }
        if(check ==s.length()) return 0;

    }
    answer =  1;
    return answer;
}

 

괄호를 넣는 문제와 유사한 형태이니 자료형인 Stack 을 먼저 떠오르는게 당연할 수 도 있다.

 

아니면,, 일단 외우자 

 

다음과 같은 코드를 통해 O(N) 으로 문제를 해결 가능하다.

public int solution(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }

    return stack.isEmpty() ? 1 : 0;
}

 

3 항 연산자를 통해 스택이 비면 1 , 남아있으면 0 을 출력한다.