[백준]9935번 문자열 폭발 - C++

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

---

단어를 만나면 lev을 부여하여 pair{문자,lev}로 스택에 넣는다.

문자열을 순서대로 순회한다. lev는 현재까지 일치하는 폭발 문자열의 수로 0부터 시작을 한다.

1. 해당 문자열의 lev 를 정한다.

    1) str[i] 와 bset[lev] 가 같다면 lev를 증가시킨 상태에서 스택에 추가한다.

    2) str[i]가 bset[0] 이라면 앞의 lev 와 관계없이 새롭게 폭발 문자열이 시작될 수도 있다. 따라서 lev를 1로 설정해준다.

    3) 위 해당사항이 없다면 lev는 0으로 설정해준다. 

2. lev 가 bset의 길이만 큼 되었다면 폭발 문자열이 나왔다는 것이므로 폭발 문자열의 길이 만큼 스택을 pop해준다.

    1) 폭발 문자열이 날라갔다면 스택의 맨 위에 저장해둔 lev를 기준으로 폭발 문자열을 찾아나간다.

    ex) 예시 처럼 (C,1) 이 있고 (C,1) (4,2) 가 없어졌다. 스택의 가장 위 lev == 1로 다음 4 가 들어오면

          str[i] == bset[lev]로 lev 가 증가하여 2가 되고 lev == bset의 길이 이므로 또 pop 된다.

    2) 만약 스택이 비어있다면 lev는 0으로 설정한다. 

---

 처음에는 재귀방식을 활용하여 풀려고 하였으나 틀렸다. 예시에 대한 답은 잘 나오지만 코드를 작성한 나조차 확신이 없어서 다르게 풀어보았다. lev를 활용하여 nested 된 구조에서 pop을 하면 이전 상태의 정보를 불러오는 방식을 생각했다. 하지만 틀렸습니다가 계속 나와서 다음에 풀어봐야지라고 생각했다. 5일 만에 다시 와서 생각해 보니 여전히 알고리즘적 문제를 생각하지 못해서 코드를 찬찬히 살펴본 결과 ans를 출력할 때 length()부터 출력을 했던 것이었다. 이렇게 되면 의도했던 것보다 한 칸이 더 출력되게 되는데 gcc -std=c++17 옵션을 컴파일을 하면 잘 나와버린 것이 화근이었다. length()-1로 고친 뒤 제출을 하니 맞았습니다가 나왔다.

 다른 블로그들을 찾아보니 모두 다 문자열을 스택처럼 활용하여 폭발문자열의 끝단어와 일치하면 폭발문자열이 맞는지 확인하는 방식을 활용하였는데 이는 불필요하게 스택을 bset의 이전 값들을 확인해야 했다. 이런 과정 없이 해당 칸 만으로 폭발 문자열이 맞는지 확인을 하고 싶었고 이렇게 풀게 되었다. 처음에 length()를 잘못했는지 모르고 다른 블로그들을 구글에서 세 페이지 정도 확인해 봤는데 하나 같이 다 같은 방법을 활용하였다. 그렇게 깔끔한 풀이는 아닌 것 같은데 왜 모든 사람들이 그렇게 풀었는지 모르겠다.