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

문제설명

알파벳 소문자로 이루어진 문자열을 가지고 시작한다. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾는다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙인다. 이 과정을 반복하여 모두 제거하면 짝지어 제거하기가 종료된다.

문자열 S가 주어졌을 때 성공적으로 수행할 수 있으면 1을, 아닐경우 0을 반환한다.

예를 들어 문자열 S = baabaa 라고

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

 

제한사항

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

입출력 예

s	result
baabaa	1
cdcd	0

 

---

코드설명

이 문제는 stack을 사용한다.

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

 

stack 이 비어있지 않고, 가장 위에 위치한 값이 다음에 와야 할 값과 같으면 pop()으로 제거한다.

스택이 비어있으면 true, 비어있지 않으면 false를 반환한다.

stack.isEmpty();

 

스택의 가장 위에있는 값이 i번째 글자와 같다면 true, 다르면 false를 반환한다.

stack.peek() == s.charAt(i);

 

즉, 스택이 비어있지않고 가장 위에 있는 값이 단어의 i 번째 글자와 같으면 stack.pop()으로 그 값을 제거한다.

if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
    stack.pop();
}

 

그렇지 않다면 i번째 글자를 스택에 추가한다.

else {
    stack.push(s.charAt(i));
}

 

마지막으로 stack.isEmpty()를 사용하여 stack이 비어있다면 1, 비어있지 않다면 0을 반환한다.

return stack.isEmpty() ? 1 : 0;

---

 

코드

import java.util.Stack;

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

        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }

}

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges