ペアリング削除

2343 ワード
コーディングテスト プログラマ テキストリンク
質問する

もんだいぶんせき
同じ文字が2つある場合は削除します.削除後に同じ文字が2つ存在する場合は、存在しないまで削除します.同じ文字が2つ削除され、残りの文字がない場合は1を返し、ある場合は0を返します.
に答える
コアは2文字を削除します.3個4個...nは連続するすべての文字列を処理し,String.substring()を用いて前後の文字列を再結合するが,効率の問題からStackを用いて解決した.
Stack
問題はn개의 연속된 동일한 문자ではなく、2개의 연속된 동일한 문자です.現在の文字列を比較するだけで、次の文字列を比較する必要はありません.スタックは効率が高いだけでなく、理解しやすい.
		Stack<String> stack = new Stack<>();
        String[] arr = s.split("");
        
        for(String input : arr){
            if(!stack.isEmpty() && stack.peek().equals(input)) //2개가 붙어 있는 짝
                stack.pop();
            else // 다른 문자
                stack.push(input);
        }
空の場合、または스택의 TOPにある文字と異なる場合は스택.push()であり、逆に스택의 TOPにある文字と同じ場合は스택.pop()であり、前の文字と比較するだけでよい.
コード#コード#
import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        Stack<String> stack = new Stack<>();
        String[] arr = s.split("");
        
        for(String input : arr){
            if(!stack.isEmpty() && stack.peek().equals(input)) //2개가 붙어 있는 짝
                stack.pop();
            else // 다른 문자
                stack.push(input);
        }
        
        if(stack.isEmpty()) //비어있다면, 모두 짝지을 수 있다면
            answer = 1;
        
        return answer;
    }
}
GitHub
https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%9E%90%EB%B0%94/Level2/%EC%A7%9D%EC%A7%80%EC%96%B4%EC%A0%9C%EA%B1%B0%ED%95%98%EA%B8%B0.java
22035プログラマーハザード数
nefu 1116