[PCCP] 스택 · 큐 · 정렬 · 그리디 알고리즘 [1]

▼ Why ?

스택(Stack) 관련 내용을 정리하면서 스택을 활용하기에 좋은 문제 유형 중 하나가 짝꿍(Pair)을 찾고 이웃했을 때 충돌해서 사라지는 경우라 했는데, 이번에 이것이 어떤 경우를 말하는 것인지 알기 위해 관련 문제를 하나 풀어봤다.

---

▼ Backspace

 

문제 정보

매개변수 s에 문자열이 주어지면 이웃한 두 개의 문자가 같으면 두 문자를 제거합니다.

이 과정을 반복해서 최종적으로 남는 문자만으로 이루어진 문자열을 반환하는 프로그램을 작성하세요.

만약 "acbbcaa"라는 문자열이 주어진다면 최초 bb가 연속되어 있어 제거하고 나면 "accaa"가 되고, 다시 cc가 연속되어 제거하면 "aaa"가 되고 "aa"연속되어 제거하면 "a"가 최종적으로 남습니다.

 

제한사항

• 문자열 s의 길이는 100,000을 넘지 않습니다
• 문자열 s는 소문자로만 이루어져 있습니다

 

입출력 예

 

어떻게 해결해야 할까 ?

1. 앞서 말했듯이 짝꿍(Pair)이 이웃하게 됐을 때 충돌하여 사라지는 문제이므로 스택(Stack)을 활용하면 어렵지 않게 해결할 수 있을 것 같다
2. 문자열의 처음 문자부터 순차적으로 하나씩 꺼내 ' push() ' 를 해주는데, 이전과 같은 문자일 경우엔 해당 문자를 ' push() ' 하지말고 Stack에서 ' pop() ' 해주면 된다

 

해결 코드

class Solution {
    public String solution(String s) {
        Stack<Chracter> strStack = new Stack<>();
        
        for(char ch : s.toCharArray()) {
            if(!strStack.empty() && ch == strStack.peek) {
                strStack.pop();
                continue;
            }
            
            strStack.push(ch);
        }
        
        String answer;
        StringBuilder sb = new StringBuilder();
        
        for(char ch : strStack)
            sb.append(ch);
            
        answer = sb.toString();
    }
}

 

---

▼ 정리

 

• 이전 문제와 해결방법이 크게 다르지 않았고, 이웃한 게 충돌해서 사라지는 경우가 어떤 것을 말하는 것인지 정도만 알고 넘어가면 될 것 같다