BOJ) 문자열 폭발 (9935 번)

문자열 폭발

9935번: 문자열 폭발

이전에 시도했다가 실패했던 문제다.

replaceAll이라는 좋은 메소드를 제공해주는데 굳이 구현을 해야할까? 싶어서 시도했었는데 역시나 시간초과였다. 자바는 문자열에 참 약하다...ㅠ

어떻게 풀어야할까 생각하다가 문제의 하단에 있는 알고리즘 분류를 봤는데 스택이 있었다.

그래서 스택을 이용해서 먼저 문제를 풀었다.

 

문자열을 돌면서 문자를 스택에 넣어주는데, 넣을 차례의 문자가 폭탄의 마지막 문자와 같은 경우 기존 스택에서 값을 꺼내면서 차례대로 폭탄과 같은지 확인해주었다. 이 때, 폭탄이 아닐 수도 있기 때문에 값을 저장할 스택을 따로 선언해서 입력하고 있던 스택에서 꺼낸 문자를 저장해주었다.

폭탄이 아니면 임시로 저장한 스택에서 문자를 다시 입력 중이던 스택에 입력해주었다.

 

문제는 풀었지만 뭔가 비효율적이라고 생각이 들었다.

그래서 스택 개념을 떠올리면서 배열과 인덱스를 이용해서 문제를 다시 풀었다.

위의 방식과 같이 문자열을 돌면서 배열에 차례대로 저장해주고, 배열에 폭탄이 존재하는지 확인해줬다.

만약, 폭탄이 존재하면 인덱스를 폭탄의 크기만큼 줄여주어 새로운 값을 폭탄 위에 저장할 수 있도록 설정해주었다.

 

확실히 스택을 사용하는 것 보다, 배열과 인덱스를 통해 문제를 푸는게 시간과 공간 효율성에 아주 좋다.