[프로그래머스] 짝지어 제거하기 (stack)

 

문제 설명

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

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

b aa baa → bb aa → aa →

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

 

 

제한사항

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

 

1. 문자열 s를 리스트로 받아

2. 포문을 역순으로 돌며 현재 값과 직전의 값이 같으면 삭제 

2-1. 삭제를 실행했다면 isDeleted 상태 true로 변경

3. 리스트의 크기가 0 (=문자열을 모두 제거한 상태, 리턴값 1) 이거나

    isDeletetd 상태가 false일 경우(=제거할 수 있는 문자열은 모두 제거한 상태, 리턴값 0) 반복문 종료

 

로 알고리즘을 짜고 실행을 했는데요..

import java.util.*;
class Solution{
    public int solution(String s){
        int answer = -1;
        
        List<Character> sList = new ArrayList<>();
        boolean isDeleted = false;
        for (char c : s.toCharArray()){
            sList.add(c);
        }
        while(true){
            isDeleted = false;
            for(int i = sList.size() -1 ; i >0 ; i--){
                if(sList.get(i).equals(sList.get(i-1))){
                    sList.remove(i);
                    sList.remove(i-1);
                    i--;
                    isDeleted = true;
                }
            }
            
            if(sList.size() == 0){
                answer = 1;
                break;
            }else if (!isDeleted){
                answer = 0;
                break;
            }
        }
        return answer;
    }
}

 

효율성이 4.9로 뜨며 실패를 했습니다..😭

 

다른 방법을 찾던 중 현재 문제가 요구하는 것을 정확히 실행시킬 수 있는 stack을 알게 되었습니다.

 

Stack은 LIFO(Last In, Frist Out)구조로, 가장 나중에 들어온 것부터 먼저 나가는 자료구조 인데요, 

 

Stack<Character> stack = new Stack<>();

 

이렇게 선언하고 사용하면 됩니다. (저는 char로 활용할 거기 때문에 Character로 선언했습니다.)

 

이번에 사용할 메서드는

push(n)	맨 위에 값 넣기
pop()	맨 위의 값 꺼내기 + 삭제
peek()	맨 위의 값 확인하
isEmpty()	비어있는지 확인(반환값 : true/ false)

 

입니다.

 

1. 스택을 하나 만들어주고

2. 문자열 s를 배열로 하여 스택에 하나하나 집어 넣습니다.

2-1. 스택이 비어있지 않고 직전의 값이 현재 넣고자 하는 값과 같다면 직전에 넣은 값을 삭제합니다. 

2-2. 그게 아니라면 해당 값을 넣습니다.

3. 스택이 비어있는지를 확인하고, 비어있다면 1을, 아니라면 0을 리턴합니다.

import java.util.*;
class Solution{
    public int solution(String s){

        Stack<Character> sStack = new Stack<>();
        
        for( char c : s.toCharArray()){
            if(!sStack.isEmpty() && sStack.peek() == c){
                sStack.pop();
            }else{
                sStack.push(c);
            }
        }
        return sStack.isEmpty() ? 1 : 0;
    }
}

 

스택을 사용하니 무한 반목문을 사용하지 않고 해결할 수 있었습니다.