BOJ 9935 문자열 폭발

문자열 strA와 '폭발 문자열' strE가 주어지면 strA에 포함된 strE가 폭발해서 사라지고 남은 문자열끼리 이어진다. 근데 이어지면서 만약 strE가 또 생긴다면 그 것 역시 폭발한다.
이런 식으로 폭발이 다 끝났을 때 최종적으로 남는 문자열을 구하는 문제이다.

스택을 사용해야 하는 문제인데,,, 스택을 사용해서 풀어야 한다는 사실을 알고 있음에도 어떻게 풀어야 할지 쉽게 떠오르지 않는다. 생각을 해보자... 음 그냥 백준님 풀이를 봐야겠다.

뭐 여기서 잠깐 내 생각을 적자면... 이 문제를 혼자 힘으로 생각해서 푸는 것이 제일 좋겠지만 시간도 많지 않고(그렇다고 내가 시간을 잘 쓰는 건 아니지만...) 또한 계속 고민하다가 모르겠거나 생각이 잘 안나면 힘만 빠지고 공부에 대한 흥미가 떨어지기도 한다. 그렇기 때문에 나는 천 가지 정도의 범죄 사건만 자세히 알고있으면 어떤 사건이든 해결하지 못할 것이 없다던 셜록홈즈의 말처럼 ... 일단 많은 문제를 접하고, 이해하고 잊어버리지 않는 것에 중점을 두고 공부하려고 한다. 물론 그렇다고 아예 생각도 안 한다는 것은 아니다. 뭔가 풀 수 있을 것 같은 것이나 조금 더 생각하면 될 것 같다하는 문제들은 하루 종일 생각하기도 한다.
그리고 이렇게 답이나 풀이를 보더라도 확실하게 이해해서 내 꺼로 만드려고 노력한다. 그리고 사실 풀이를 보더라도 이해하고 내 꺼로 만들려면 많은 생각을 해야하고, 절대 쉽지 않다.
그리고 가장 큰 문제가 내 힘으로 고민해서 풀지 않은 문제는 빨리 잊어버린다는 것인데, (사실 고민해서 풀어도 잊어버리긴 한다) 그 문제를 방지하기 위해 이렇게 블로그에 적는 것을 시작했다. 내가 나중에 기억이 안 날 때 글을 읽고 다시 접근할 수 있을 정도로 쓰고 있다. 그리고 복습이 가장 중요할 것이다.

쉽지 않은 여정이지만 조금씩 실력이 늘고 있다고 생각한다. 그리고 가장 큰 문제는 나 자신이다. 내가 열심히 해야 하고, 즐겨야 한다. 문제 풀면서 재미를 느끼고, 억지로 하는 것이 아닌, 하고 싶어서 , 재밌어서 해야 한다.

자 이제 문자열 폭발 풀이를 써보겠다.

stack을 이용하는데, 정말 1차원적으로? 너무 단순하게? ... 문자열을 스택에 넣었다가 어떻게 조작해서 스택에 남은 문자열을 출력할 생각만 했는데, 그러다보니 폭발 문자열을 찾기도 힘들고... 그냥 꽉 막혔었다.

stack에는 문자를 넣는 것이 아니라 그 문자의 문자열에서의 index와 그 문자에 해당하는 폭발 문자열의 문자의 index를 넣는다.
먼저 폭발 문자열이 abc라고 하면, a, b, c 이렇게 3개가 연속적으로 붙어있어야 폭발 문자열의 효력을 지니므로 먼저 a가 필요하다. 그래서 항상 a(폭발 문자열의 첫번째)는 발견될 때마다 stack에 넣어준다. 그리고 a이외의 문자가 발견되면, 방금 전의 문자가 무엇인지 체크한다. 즉 stack에서 가장 위에 있던 문자가 a이외의 문자와 비교했을 때 폭발 문자열을 만들 수 있게 바로 앞 index이면(폭발 문자열의 index) 그 문자도 stack에 넣어준다. 하지만 만약 폭발 문자열을 만들 수 있는 문자가 아니라면 이제 그 문자 앞의 문자들(stack에 있는 폭발문자열의 가능성을 가진 문자들)은 아무런 의미가 없어지므로 그냥 다 stack에서 지워버린다. 이런 식으로 가면서 폭발 문자열의 가장 마지막 문자까지 만들어지면 stack에서 그 부분만 지운다. 그럼 지워진 후에 폭발 문자열이 또 만들어 질지는 어떻게 알까? 바로 stack에는 폭발 문자열의 index가 들어가있기 때문에 다음에 어떤 문자가 와야 폭발 문자열이 만들어질지 알 수 있다. 게다가 폭발 문자열이 만들어져서 지울 때는, 같이 넣었던 원래 문자열에서의 index를 기록해놓고, 나중에 출력할 때 그 (폭발한 것으로) 기록해놓은 index들만 빼고 출력하면 되는 것이다.

문자 대신 index를 넣되 폭발 문자열의 가능성이 있는 경우만 index를 넣어서 index만으로 폭발 문자열이 만들어지는지 파악할 수 있게 하는 것이 좋은 방법인 것 같다.

아 그리고, 예외의 경우로는 폭발 문자열의 길이가 1인 경우인데, 이 경우는 for문으로 따로 처리하면 된다.
음 그리고 깜박할 수 있는 것 : 문자열이 다 지워지는 경우에는 FRULA를 출력하라고 되어있다.

출처 : 백준님 강의, 강의 자료

그리고 맞은 사람 목록에서 cubelover님 코드를 봤는데.. 엄청 간결하다.
주어진 문자열의 문자를 앞에서 부터 하나씩 정답 str 배열에 추가하면서 폭발 문자열의 문자 수만큼 (문자 하나 추가할 때마다) 폭발 문자열이 성립되는지 검사한다. 그리고 성립되면 폭발 문자열 개수만큼 앞의 index에서 부터 다음 문자를 받기 시작한다.(즉 폭발 문자열을 제거한 것이나 마찬가지) 그리고 중요한 부분은 폭발 문자열이 성립되지 않는 경우인데,  이 부분은 내가 직접 구현을 해보고 생각도 해봐야 할 것 같다. 아 폭발 문자열이 성립되지 않는 경우는 생각할 필요가 없구나... 그냥 하나 하나씩 문자 추가될때마다 폭발 문자열이 만들어지는지 확인하고 만들어지면 폭파시키면(제거하고) 되는 것이다. 좀 헷갈렸다. 와...정말 간단한 방법인데(이해하고 보니..) 왜 이런 방법을 생각 못했을까... 정말 대단하신 것 같다.
이 방법의 시간 복잡도는 O(폭발 문자열의 길이 * 주어진 문자열의 길이) 가 되겠지만, 워낙 간단하다보니 시간이 많이 걸리지도 않는 것 같다.

아 그리고 위에서 stack으로 구현하는 방법은 시간 복잡도가 최악의 경우... 만약 문자열의 모든 문자가 다 폭발해서 지워지는 경우... O(2*n)정도 될 것 같다.