[프로그래머스 연습문제 level_2 ] 짝지어 제거하기

문제 설명

 

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

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

b aa baa → bb aa → aa →

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

제한사항

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

 

 

입출력 예

 

baabaa	1
cdcd	0

입출력 예 설명

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

 

 

---

 

 

처음 생각

 

스택을 모르는 상태로 접근하려 했을 때는, 문자열을 넣은 리스트에서 문자열 i 번째와 i+1 번째가 같으면 삭제하고,

 

삭제되면 다시 처음부터 비교하는 식으로 생각했지만 잘 되지않았다.

 

다른 블로그들을 통해 스택을 이용하면 쉽게 풀 수 있다는 것을 알았고 Java의 자료구조중의 하나인 Stack을 공부했다.

 

 

내가 푼 방법

 

문제 설명대로 문자열에서 같은 알파벳이 2개 붙어있는 짝을 찾아 제거하는 식으로 생각하면 문제를 풀 수 없다. 

 

짝을 찾아 제거한 후 남은 알파벳 중, 가장 가까이 있는 왼쪽 알파벳과 그 다음 알파벳을 비교하는 것을 반복하는

 

알고리즘 즉, 가장 최근의 알파벳과 그 다음의 알파벳을 비교한다는 핵심을 안다면 스택을 사용하는 것이 효율적이다. 

 

연속한 알파벳이 서로 다르다면 스택에 넣고, 스택의 최상위값과 다음 알파벳을 비교해

 

같으면 스택에서 삭제, 다르면 추가하는 식으로 풀어야한다. 

 

 

 

- 스택 사용

import java.util.Stack;
class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        // 스택생성
		Stack<Character> stack = new Stack<>();
        //스택에 첫번째값넣기
        stack.push(s.charAt(0));
        
        for(int i=1; i<s.length(); i++){
        	// 스택이 비어있거나 s의 알파벳이 스택의peek값과 같으면 push하기
            if(stack.empty() || s.charAt(i)!=stack.peek()) {
                stack.push(s.charAt(i));
                }
            // s의 알파벳이 스택의 peek값과 다르면 pop하기
            else if(s.charAt(i)==stack.peek()) {
                stack.pop();
            }
        }
        // 스택에 남은게 없으면 성공, 아니면 실패
        if(stack.size() ==0) answer = 1;
        else answer =0;
        
        return answer;
    }
}

 

 

 

- 리스트 사용

import java.util.ArrayList;
import java.util.Arrays;
class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        // 리스트 생성
		ArrayList<Character> list = new ArrayList<>();
        // 리스트에 처음값 넣어두기
        list.add(s.charAt(0));
        
        for(int i=1; i<s.length(); i++){
        	// 리스트에 아무것도없거나, s의 알파벳과 리스트의 마지막값이 다르면 add하기
            if(list.size()==0 || s.charAt(i) != list.get(list.size()-1)) list.add(s.charAt(i));
            // s의 알파벳과 리스트의 마지막값이 같으면 리스트의 마지막값 remove하기
            else if(s.charAt(i) == list.get(list.size()-1)) list.remove(list.size()-1);
        }
        
        // 리스트에 아무것도 남지않았으면 성공, 아니면 실패
        if(list.size() ==0) answer = 1;
        else answer =0;
          return answer;
    }
}