231022 TIL - 프로그래머스 짝지어 제거하기

오늘은 프로그래머스 알고리즘 문제를 풀었다.

오늘 푼 문제는 lv2 짝지어 제거하기 이다.https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

이 문제도 어제 푼 문제와 같이 Stack을 이용해서 풀이하였다.

import java.util.*;

class Solution{
    
    public int solution(String s){
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        // for(s의길이){
        //     stack에 s.charAt()추가 s.charAt()이 s.peek()과 같다면 추가하지 않고 pop
        // }
        for(int i=0; i<s.length(); i++){
            if(stack.isEmpty()){
                stack.push(s.charAt(i));
            } else if(stack.peek() == s.charAt(i)){
                stack.pop();
            } else{
                stack.push(s.charAt(i));
            }
        }
        if(stack.isEmpty()){
            answer = 1;
        }
        return answer;
    }
}

여러 튜터님들과 매니저님들의 말씀대로 먼저 말 또는 슈도코드로 풀이방법을 적은 뒤 그걸 자바 언어로 구현해서 풀이하였다.  

 먼저 Stack이 비어있다면 문자열s 의 첫 문자를 추가하고 비어있지 않은 경우에 Stack에 가장 최근에 추가한 문자(peek)와 이번에 추가해야 할 문자(s.charAt(i))가 같다면 둘이 짝이므로 추가하지 않고 기존에 있던것을 pop()하여서 둘 다 Stack에없게 하였다. 그리고 Stack이 비어있지 않지만 가장최근에 추가한 문자가 추가해야할 문자가 같지 않다면 짝이 아니므로 Stack에 추가를 하는 구조로 알고리즘을 짰다. 이것을 s의 길이동안 반복하였을 때 남은 문자가 없다면 모두 짝을 지어서 Stack에 남아있지 않으므로 1을 return, Stack에 문자가 남아있다면 짝을 짓지 못한것이므로 2를 return하였다. 

 어제 푼 괄호의 짝이 맞는지 구분하는 문제도 그렇고 오늘 같은 문자 두 개를 짝지어서 제거하는 것도 그렇고 Stack은 짝을 짓는 문제를 푸는데 유리한 자료구조인 것 같다. 다음에도 짝을짓는 문제가 나온다면 Stack을 먼저 떠올리게 될 것 같다. 내일도 화이팅!