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

 

프로그래머스

 

1. 문제 요약

문자열 s가 주어집니다.

 

문자열 s안에 연속으로 같은 알파벳 2개가 있으면 제거하고 앞뒤로 이어 붙입니다.

해당 과정을 계속 반복하여 모든 알파벳을 제거할 수 있으면 1을 리턴하고, 없으면 0을 리턴합니다.

 

2. 접근 방법

• 제거할 수 없는 알파벳을 담을 Stack을 초기화합니다.
• 문자열을 순차적으로 방문합니다.
  • Stack이 비어있으면 현재 알파벳을 넣습니다.
  • Stack에 최근에 넣은 알파벳과 현재 알파벳이 다를 경우 제거할 수 없으므로 현재 알파벳을 넣습니다.
  • Stack에 최근에 넣은 알파벳과 현재 알파벳이 같을 경우 제거할 수 있으므로 Stack의 해당 알파벳을 제거합니다.
• 과정을 마친 후 Stack이 비어있다면 1, 아니면 0을 리턴합니다.

 

3. 파이썬

def solution(s: str):
    if len(s) % 2 == 1:
        return 0
    
    stack = []
    for char in s:
        if not(stack) or stack[-1] != char:
            stack.append(char)
        else: # stack[-1] == char:
            stack.pop()
    
    return 1 if not(stack) else 0

 

4. 자바

public int solution(String s) {
    if (s.length() % 2 == 1) {
        return 0;
    }

    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (stack.isEmpty() || stack.peek() != c) {
            stack.push(c);
        } else {
            stack.pop();
        }
    }

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