[백준] 9935.문자열 폭발 (C++)

9935.문자열 폭발

시도

• 문자열의 최대길이가 100만인 것을 보고 당연히 O(n)안에 해결해야 하겠거니 싶었다.
• 0과 1의 state를 나눠 문자열을 탐색하며
  • 처음 default state는 state 0
  • 현재 문자와 폭발 문자열의 첫 문자가 동일하면 state 1로 진입, 폭발문자열 길이 만큼 계속 비교
    • 폭발 문자열 길이 만큼 모두 비교했다면 길이 만큼 stack에서 pop
  • 문자가 다르면 state 0으로 돌아가기
• 뭐.. 아무튼 복잡하게 풀어봤는데 1차적으로 보이는 폭발 문자열을 걸러내는 것은 되지만 걸러내고 남은 문자열들이 만나 다시 또 폭발문자열을 구성할 때에 대해 해결을 하지 못한다는 문제가 생겼다.

위 방식에서는 폭발문자열의 첫 문자가 동일하면 비교를 시작 하는 식이었는데,
반대로 현재 문자와 폭발문자열의 끝 문자가 동일하면 비교하는 식으로 바꾸어 풀어보았다.

핵심

• stack 방식의 자료구조를 활용하여 폭발 문자열이 발견되면 pop, 스택에 남아 쌓여있는 값들끼리 모여 다시 폭발 문자열을 이루면 pop...
• 위 과정이 불가능 해질 때 까지 반복된다.

해설

주어진 문자열(s)와 폭발 문자열(b)이 주어진다고 하자.

1. 문자열 s를 탐색하며 문자 하나씩 stack에 push한다.
2. stack의 top이 폭발문자열 b의 마지막 값과 동일하면 폭발문자열의 길이 만큼 stack에서 pop을 시도해본다.
3. pop하여 나온 문자를 모아 거꾸로 뒤집어 만든 문자열이 폭발 문자열과 일치하는지 확인한다. (LIFO이므로 거꾸로 조합해야한다)
4. 폭발 문자열과 동일하다면 다음 수행을 이어나간다.
   폭발 문자열과 다르다면 다시 문자열을 집어 넣는다.
5. 단, 2~3에서 폭발 문자열의 길이 만큼 pop을 수행하기도 전에 스택이 빈어버린다면 수행을 멈추고 pop했던 것들을 다시 집어 넣는다.
   → 길이조차 짧으니 폭발 문자열과 다르다는 의미다.(더 접근하면 segmentation fault)
6. 수행이 끝나면 stack의 모든 값을 다시 뽑아 문자열을 완성시킨다.
   
   
   

구현

• 마지막 stack에 저장된 모든 값을 꺼내 문자열을 만들 때 편리하게 구현하기 위해 deque를 활용하였다.
• 처음에 segfault에러를 못잡아 조금 고민했는데, 스택이 이미 비었는데 폭발문자열 길이 만큼 억지로 pop하려고 했던 것이 문제였다.
  • 스택이 이미 빈다면 종료, 다시 집어 넣을 땐 꺼낸 만큼만 집어넣기
  • 아무리 많이 꺼내도 꺼낸 문자열은 최대 길이가 폭발문자열과 같으니까!