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

1.  문제 설명

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

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

b aa baa → bb aa → aa →

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

2. 제한사항

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

3. 입출력예

s	result
baabaa	1
cdcd	0

 

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

4. 풀이

Solution 1

import java.util.*;
class Solution{
    public int solution(String s) {
        // 문자열을 캐릭터형 배열에 한글자씩 담아준다.
        char[] arrCh = s.toCharArray();
        
        // Stack에 글자를 한자씩 담으면서 짝이 맞으면 빼준다.
        Stack<Character> stack = new Stack<>();
        stack.push(arrCh[0]);
        
        for(int i=1; i< s.length(); i++){
            if(stack.size() == 0) {
                stack.push(arrCh[i]);
                continue;
            }
            
            char now = stack.peek();
            char next = arrCh[i];
            
            if(now == next) stack.pop();
            else stack.push(next);
        }
        // Stack에 글자가 남아있다면 짝이 안맞은것이고, 글자가 남아있지 않으면 짝이 다 맞은것이다.
        if(stack.size() == 0) return 1;
        else return 0;
    }
}

5. 설명

문자열을 한 글자씩 탐색 하면서 전체적으로 돌아보는것이 포인트이다. 이런걸 완전탐색..? 전체탐색..? 이라고 하는것일까?

배열의 글자를 단순히 for문 돌면서 비교할 수도 있지만 stack을 써봤다.

Stack을 쓰다보니 peek이나 pop을 할 때 EmptyStackException이 발생했다.

1. pop 메서드 : stack의 가장 최근 데이터를 stack에서 가져온다. //만약 data가 없을 때 pop하면 EmptyStackException 발생
2. peek 메서드 : stack의 가장 최근 데이터를 보여준다. // 만약 data가 없을 때 peek하면 EmptyStackException 발생

그래서 처음에 stack이 비어있지 않은지 확인해주었다. 이게 포인트!

5. 결과 

Solution 1

 

6. 마치며

프로그래머스에 카카오 문제가 주로 많은데..

카카오 문제를 풀 수 있어서 좋긴한데 국어공부부터 해야 하는게 아닌가 .. 하는 생각이들 때가 있다.

그래서 사실 낮에 카카오 무슨 문제 풀다가 이해하기를 포기하고 다른 문제를 풀었다..하하

백준 알고리즘을 한번 방문해봐야겠다.