[Java] 짝지어 제어하기

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12973

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

문제 접근

스택을 이용하여 괄호 맞추기랑 비스무리하게 풀면 된다.

1. 스택이 비었거나 스택 제일 위쪽에 있는 글자랑 현재 글자랑 다르면 스택에 넣음

2. 스택 제일 위쪽에 있는 글자랑 현재 글자가 같으면 스택에서 꺼냄

3. 문자열을 모두 순회 후, 스택이 비어있으면 1 아니면 0

 

문제 상황

처음 풀었을 때는 스택을 이용하지 않았다.

StringBuilder로 현재 포지션과 다음 포지션에 있는 글자가 같으면 두개를 지우고 포지션을 앞당겨서 푸는 방식으로 했다.

이렇게 하니 정확성 테스트는 통과했는데 효율성 테스트의 모든 케이스에서 시간 초과가 났다...

어쨋든 핵심은 스택이다.

 

소스 코드

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else if (stack.peek() == ch)  {
                stack.pop();
            }
        }

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