[프로그래머스 코딩테스트] 짝지어 제거하기(Java)

  문제 설명

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

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

  b aa baa -> bb aa -> aa ->

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

 

  제한사항

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

 

  입출력 예

s	result
baabaa	1
cdcd	0

import java.util.Stack;
class Solution {
    public int solution(String s) {
        int answer = -1;
        Stack<String> stack = new Stack<>();
        for (String str: s.split("")) {
            if (!stack.isEmpty() && stack.peek().equals(str)) {
                stack.pop();
            } else {
                stack.push(str);
            }
        }
        if (stack.isEmpty()) {
            answer = 1;
        } else {
            answer = 0;
        }
        return answer;
    }
}

  Stack을 생성합니다. 문자열이 들어갈 것이므로 제네릭 타입 역시 String입니다.

  for-each문에서 split 메소드를 이용하여 s를 한 자씩 분리하여 문자열 str이 받습니다.

  if문에서 isEmpty 메소드를 이용하여 스택이 비어있는지 확인하고(스택이 비어있을 때 pop 메소드로 꺼내면 오류 발생하기 때문에 확인하는 과정이 필요함), equals 메소드를 이용하여 스택의 맨 위 원소(peek)가 문자열 str과 동일한지 확인합니다. 만약 스택이 비어있지 않고, 맨 위 원소와 str이 동일하다면 pop 메소드를 이용하여 맨 위 원소를 스택에서 꺼냅니다. 앞선 조건에 해당하지 않으면, 즉 스택의 맨 위 원소와 str이 동일하지 않다면 push 메소드를 이용하여 스택에 str을 삽입합니다.

  for문이 끝난 후 isEmpty 메소드로 스택이 비어있는지 확인합니다. 스택이 비어 있다면 모든 원소가 짝지어 제거되었다는 뜻이므로 answer에 1을 할당합니다. 앞선 조건에 해당하지 않는다면 짝이 맞지 않는다는 뜻이므로 answer에 0을 할당합니다. 평소라면 초기화 값을 0으로 지정했을 테지만, 문제에서 -1로 지정되어 있기에 건드리지 않았습니다.

 

import java.util.Deque;
import java.util.ArrayDeque;
class Solution {
    public int solution(String s) {
        int answer = -1;
        Deque<String> deque = new ArrayDeque<>();
        for (String str: s.split("")) {
            if (!deque.isEmpty() && deque.peekLast().equals(str)) {
                deque.pollLast();
            } else {
                deque.add(str);
            }
        }
        if (deque.isEmpty()) {
            answer = 1;
        } else {
            answer = 0;
        }
        return answer;
    }
}

  스택으로 풀어봤으니 데크를 이용해서 풀어보았습니다. 원리는 스택을 풀 때와 동일하고, 일부 메소드명에 차이가 있습니다. 또, 스택은 단방향이지만 데크는 양방향이므로 메소드를 이용하여 데크에 원소를 삽입하고 비교하고 제거할 때 헷갈릴 수 있으므로 방향을 분명히 구분해야 합니다.

왼쪽 스택, 오른쪽 데크를 이용한 풀이

  이전에 풀었던 문제는 스택보다 데크 사용이 월등히 좋은 결과를 냈습니다. 이번에도 기대했지만 일부 테스트 케이스에서는 오히려 시간과 메모리 측면에서 데크가 뒤떨어지는 결과를 보였습니다.

  지금처럼 단순한 문제의 경우에는 스택으로 풀어도 무방하고, 조금 더 많은 기능을 필요로 할 경우에는 데크로 풀면 될 듯 합니다. 저는 많은 연습이 필요하기 때문에 겸사겸사 풀어봤습니다. 항상 데크가 더 낫다고 생각했는데, 꼭 그렇지만은 않은 듯합니다.

 

  스택과 데크를 이용하여 푼 다른 문제

  [프로그래머스 코딩테스트] 컨트롤 제트(Java) https://sigfriede.tistory.com/118