자바 Stack의 효율성

프로그래머스 Level2의 문제인 짝지어 제거하기 문제
해결 방법으로 StringBuilder로 중복되는 문자가 올 경우 해당문자 2개를 삭제하는 방법으로 접근했다.

처음 해결 코드

class Solution {
    public int solution(String s) {
        StringBuilder sb = new StringBuilder(s);
        
        for (int i = 0; i < sb.length() - 1; i++) {
            if (sb.charAt(i) == sb.charAt(i + 1)) {
                sb.deleteCharAt(i);    
                sb.deleteCharAt(i);    
                i = -1;                
            }
        }

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

하지만 이렇게 해결하니 예제는 통과 되었지만 효율성 검사에서 통과하지 못했다. 그 이유는 한번 반복하는데 여러번 돌기 때문 만약 문자의 길이가 길수록 반복하는 횟수가 많아져서 그런것 같았다.

그래서 생각한것이 스택을 사용하여 만들어진 문자열을 가지고 반복하기 보다는 검사 후 문자를 만드는 방식으로 생각했다.

스택

스택은 가장 나중에 들어온 데이터가 가장 먼저 빠져나가는 후입선출 구조로 되어 있어, 프로그래밍에서 데이터가 입력된 순서대로 처리되는 것이 아닌, 가장 나중에 들어온 데이터를 먼저 처리할 때 사용한다.

스택 특징

• 데이터를 하나씩만 다룰 수 있다.
• 후입선출의 데이터 구조를 가지고있다.
• 단방향 데이터 입출력 구조를 가지고 있다.

데이터 추가 및 삭제

• 추가 : add(), push()
• 삭제 : pop()

push와 add의 차이

• push()는 스택의 최상단에 데이터를 추가하는 함수
• add()는 List의 마지막에 데이터를 추가하는 함수
• 두 함수가 기능은 비슷하지만 스택의 LIFO의 명확성을 주기 위해서는 push() 함수가 더 적합하다.

수정 후 코드

import java.util.Stack;

class Solution {
    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;
    }
}

이렇게 스택이 비어있지 않으면서 스택의 마지막 데이터의 값을 불러오는 peek()을 사용하여 반복문을 이용하여 문자가 같으면 삭제하고 추가하지 않도록 하여 해결하였다.
이렇게 하니 확실히 실행시간이 줄고 유효성 검사까지 통과하였다.

해결 후 다른분들의 풀이를 보니 많이들 스택을 이용하여서 푸셨고, List를 사용하여 푸신분도 계셨다.