[알고리즘]프로그래머스 12973번 - 짝지어 제거하기

프로그래머스 12973번 - 짝지어 제거하기

프로그래머스 12973번 - https://programmers.co.kr/learn/courses/30/lessons/12973

 

요구사항

1. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾은 후 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.

2. 1번 과정을 반복해서 문자열을 모두 제거할 수 있으면 1을, 아니면 0을 반환하라.

 

요구사항 분석 및  풀이과정

연속된 문자열을 모두 제거하는 문제이며 전형적인 스택 문제입니다,

올바른 괄호 쌍을 찾을 때 스택을 사용하는 방법과 동일한 방법으로 구현하면 됩니다.

 

1. 문자열의 첫 문자부터 순회하여 만약 스택이 비었다면 문자를 추가합니다.

 

2. 스택이 비어있지 않다면 스택의 가장 위의 문자와 현재 문자가 같은지 확인합니다.

(같은 알파벳 2개 붙어있는 짝을 확인하는 작업)

 

3. 같다면 스택의 가장 위의 문자를 제거하고, 현재 문자도 스택에 넣지 않습니다.

(같은 알파벳 2개 붙어 있는 짝을 제거하는 작업)

 

4. 2번부터 문자열의 모든 문자에 대하여 반복합니다.

 

5. 4번의 작업이 끝난 후 스택이 비었다면 모두 제거된 것을 의미하고, 비어있지 않다면 실패한 것입니다.

 

소스코드 작성

import java.util.ArrayDeque;

class Solution
{
    
    public int solution(String s)
    {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        for(char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.getLast() == c) {
                stack.pollLast();
            } else {
                stack.offerLast(c);
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

 

결과

 

소스코드 깃허브 주소

링크