프로그래머스 - 짝지어 제거하기 (Java)

 

문제 개요

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

제한 사항

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

 

예시 : "baabaa" -> "bbaa" -> "aa" -> ""

---

 

풀이

단순히 생각했을 때 배열을 사용해서 1회 루프를 돌린다고 하면 중복되는 항목 하나를 지울 수 있다.

하지만 이는 정말 단순히 생각한 경우이고, 사실 처음에 생각했던 것은 위의 루프를 반복적으로 돌리면서 앞뒤로 같은 문제가 있는 것들을 다 지워주자는 것이었다.

이미 해본 사람도 있겠지만 이러면 시간초과가 발생할 확률이 크다.

물론 아닌 경우도 있지만 나의 경우 시간초과가 발생하지 않더라도 효율성 테스트가 통과되지 않았다.

 

프로그래머스 문제를 풀다보면 하단의 질문하기 버튼을 클릭해서 정답자들의 조언이나 오답자들의 질문을 볼 수 있는데, 나의 경우는 스킬 체크에서 이 문제를 직면하고 풀지 못했다 보니 질문하기에서 힌트를 얻고 싶었다.

누군가의 질문을 보니 나처럼 풀지 않고 String 값을 누적하는 방식으로 접근한 것처럼 보였다. 물론 그분도 오답이라서 올리셨겠지만, 나에게는 좋은 힌트가 되었다.

 

간단한 문제였다.

매개변수로 넘어온 String 값을 누적해서 쌓은 뒤에 가장 마지막에 있는 두 개를 비교해서 같으면 지우도록 만들면 되는 것이다.

 

그런데 이는 잘보면 스택으로 풀 수 있고, Java에서 지원하는 Stack<>을 사용하면 편하게 풀 수 있다. 

이는 나도 위의 방법으로 문제를 해결한 뒤에 다른 사람의 풀이에서 발견한 것이고, 앞으로는 문제를 해결하는 과정에서 Stack을 고려할 수 있도록 노력해야겠다.

 

---

 

코드

 

스택을 사용한 해결

import java.util.*;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (stack.isEmpty()) {
                stack.push(c);
            } else if (stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        if (stack.isEmpty())
            return 1;
        return 0;
    }
}

 

String을 사용한 해결

import java.util.*;

class Solution {
    public int solution(String s) {
        StringBuffer value = new StringBuffer();

        for (int i=0 ; i<s.length() ; i++) {
            value.append(s.charAt(i));
            if (value.length() < 2)
                continue;

            int length = value.length();
            if (value.charAt(length-1) == value.charAt(length-2))
                value.delete(length-2, length);
        }
        if (value.length() == 0)
            return 1;

        return 0;
    }
}

 

---

 

제출 결과