2022-01-11 / 짝지어 제거하기

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

 

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

입출력 예

s	result
baabaa	1
cdcd	0

 

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

 

기본 코드

class Solution
{
    public int solution(String s)
    {
        int answer = -1;

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("Hello Java");

        return answer;
    }
}

 

 

정답 코드

import java.util.*;
class Solution{
    public int solution(String s) {
 
        Stack<Character> stack = new Stack<>();
 
        for (int i=0; i<s.length(); i++) {
            if (stack.empty()) stack.push(s.charAt(i));
            else {
                if (stack.peek() == s.charAt(i)) stack.pop();
                else stack.push(s.charAt(i));
            }
        }
 
        if (stack.empty()) return  1;
        else return  0;
        
    }
}

 

 

 

 

 

---

 

 

문자열 안에 중복되는 문자가 짝지어 있다면 지우고, 최종적으로 문자열이 사라질 수 있는지 묻는 문제이다.

 

처음에 문제를 보자마자 생각난건 ArrayList였다. 하지만 효율성에서 처참히 실패..

 

import java.util.*;

class Solution{
    public int solution(String s)
    {
        ArrayList<String> str = new ArrayList<String>(Arrays.asList(s.split("")));
        
        for(int i=1; i<str.size(); i++){
            if(str.get(i).equals(str.get(i-1))){
                str.remove(i);
                str.remove(i-1); 
                i=0;
            }    
        }
    if(str.size() == 0)  return 1;
    else return 0;
    }
}

효율성을 높여 푸는 방법을 찾아봐야겠다. 그래서 찾아보니 Stack을 사용하면 문자를 쉽게 빼고 넣을 수 있다고 한다. Stack을 활용해서 풀어본 결과는 깔끔하게 성공!

 

stack이 비었다면 stack에 문자를 넣어준 후, stack의 마지막 인덱스에 있는 문자와 i번째 문자를 비교하여 같으면 지우고 다르면 추가한다. 이 과정을 거친 후 stack이 비었다면 성공, 안비었다면 실패이다.

 

if (stack.empty()) stack.push(s.charAt(i));

stack이 비었다면 기준이 되는 문자를 넣어주기 위해 push한다.

Stack에 요소를 넣을 때는 Stack.push(value)를 사용한다. 이때 가장 위에 추가된다.

 

if (stack.peek() == s.charAt(i)) stack.pop();

 stack의 가장 위에 있는 요소와 문자열  s번째 문자가 같으면 가장 위에 있는 요소를 지워준다. 지우고 나서 만약 비었다면 또다시 push하고, 비지 않았다면 해당 문장을 반복한다. 

Stack의 요소를 지울 때는 Stack.pop()을 사용한다. 이때 가장 위에 있는 요소가 지워진다.

 

이런 과정을 거치고 나면 최종적으로 stack은 비거나 문자가 있거나 둘 중 하나이다. 빈 경우는 문자들이 같아 모두 pop된 경우이고, 비지 않았다면 pop이 되지 않았다는 뜻 즉, 짝지어 제거하기를 실패한 경우이다. 

 

 

 

 

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