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

▼ Why ?

일단, 스택을 활용하는 기본 문제부터 풀어보려고 한다.

---

▼ Backspace

 

문제 정보

현수는 주어진 문자열의 문자 순서대로 키보드 자판의 문자를 쳐 화면에 s문자열을 작성합니다.

문자열에는 '#'문자가 있는데 이 문자는 Backspace키를 의미합니다.

매개변수 s에 현수가 키보드 자판을 쳐야할 순서인 문자열이 주어지면 현수가 s문자열을 작성 했을 때 최종적으로 화면에 작성된 문자열을 반환하는 프로그램을 작성하세요. 화면에는 적어도 문자 한 개는 작성되어 있습니다.

 

제한사항

• 문자열 s의 길이는 1,000을 넘지 않습니다.

 

입출력 예

 

어떻게 해결해야 할까 ?

1. 일반적인 Backspace의 동작 원리는 Stack과 별반 다르지 않기 때문에, Stack의 연산을 활용해보자
2. 문자열에서 받아온 문자를 하나씩 Stackdp ' push() ' 해주고, 문자 '#'이 확인될 때마다 Stack에서 데이터를 ' pop() ' 해주면 될 것 같다
3. 단, 데이터를 꺼내기 전에 스택이 비어있지는 않은지 먼저 확인을 해줘야 한다

 

해결 코드 0

• 반환타입이 String이기 때문에, Stack에서 문자를 하나씩 꺼낼 때마다 문자열을 수정하고 해당 문자열을 반환해줘야 해서 StringBuilder를 이용헀다

class Solution {
    public String solution(String s) {
        Stack<Character> inputStack = new Stack<>();
        
        for(char c : s.toCharArray()) {
            if(c == '#' && !inputStack.empty()) {
                inputStack.pop();
                continue;
            }
            
            inputStack.push(c);
        }
        
        Iterator<String> itr = inputStack.iterator();
        StringBuilder sb = new StringBuilder();
        
        while(itr.hasNext()) {
            sb.append(itr.next());
        }
        
        String answer = sb.toString();
        
        return answer;
    }
}

 

해결 코드 1

• Iterator를 이용하지 않고 Stack의 요소에 접근하는 방법도 있다는 것을 알고 코드를 조금 수정해봤다

class Solution {
    public String solution(String s) {
        Stack<Character> st = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '#' && !st.isEmpty()) {
                st.pop();
                continue;
            }
            
            st.push(c);
        }
           
        StringBuilder sb = new StringBuilder();
        
        for (char c : st) sb.append(c);

        return sb.toString();
    }
}

 

---

▼ 정리

 

• Stack을 다룰 때엔 Stack이 비어있으면 문제가 있는 작업인지 생각하고 미리 체크해야 하는 것을 깜빡하지 말자
  
  
• 문자열을 다룰 때는 StringBuilder class를 잊지말고 활용하자
  
  
• Stack의 요소에 반복적으로 접근하는 방법은 Iterator class를 이용하는 것 말고도 여러가지가 있다