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

풀이

키워드

• Stack

  스택은 처음 사용해보았다. 스택이라는 개념은 알고 있었지만, 알고리즘에 사용해본 경우는 처음이였다. 스택을 사용하지 않고 재귀를 이용해 풀었을 때는 틀리는 케이스들도 있었고 무엇보다 효율성을 통과하지 못했다. 스택을 사용한 경우,  일단 무엇보다 코드가 간결해졌다. 뭔가 재귀로 풀어야 할 문제들을 만났을 때, 재귀로 풀기 전 스택을 한번 고려해보면 좋을 것 같다고 느꼈다.

 

  우선 원리는 간단하다. 입력받은 문자열 s를 한 문자씩 탐색해나간다. 그리고 조건에 따라 문자를 스택에 넣거나(push()) 스택에서 문자 하나를 빼낸다(pop()).

 

  push() 조건

• Stack이 비어있거나 || 스택의 윗부분이 현재 문자와 다를 경우

  pop() 조건

• Stack이 비어있지 않을 경우 && 스택의 윗부분이 현재 문자와 같을 경우

 

이렇게 되면, 문자열이 두번 짝지어져서 stack에 연속으로 쌓이는 경우가 생기면 pop()에 의해서 이들이 제거된다. 즉 마지막에 Stack이 비어있다면 짝지어 제거하기가 성공한 것이고, 하나라도 남아 있다면 실패한 것이다.

---

코드

import java.util.Stack;

class Solution
{
    public int solution(String s)
    {
        Stack<Character> st = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (!st.isEmpty() && st.peek() == c) {
                st.pop();
            }
            else {
                st.push(c);
            }
        }
        return st.isEmpty() ? 1 : 0;
    }
}

 

---

출처 : https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기