오랜만에 올리는 포스트이다. 최근에 코딩 테스트도 끝냈고 여유를 가지고 있던중에 오늘 컨디션이 좀 안좋아서 문제를 푸는데 머리가 굉장히 안돌아갔었다. 그래도 이번주에 또 한번 코딩테스트가 있으니깐 내일부터는 다시 제 페이스 찾아가지고 전에 했던것처럼 폼을 많이 올려야겠다.
난 고질적으로 stack 태그가 들어간 문제는 안풀었다. 애초에 많이 나오지도 않는 유형이기도 하고 stack은 원리 자체가 굉장히 쉽고 굳이 많은 생각이 들어간다고 생각하지 않았기 때문이다. 그런데 이런 평범한 문자열 관련된 문자를 풀고있는데 스택에 대한 개념이 효율적으로 문제를 푸는데 얼마나 도움이 되는지 느꼈었다.
문제가 요구하는건 굉장히 간단하다. 가장 먼저 오리지널 문자열이 나오고 그 다음줄에는 폭팔해야하는 단어가 나온다. 오리지널 문자를 읽으면서 더 이상 폭팔시킬수있는 단어가 나오지 않을때까지 폭팔 시키면 된다.
초반에 생각했던 가장 직관적인 풀이 방법이었다. 첫 for 룹으로는 오리지널 단어를 탐색하면서 만약 단어가 하나라도 폭팔 단어랑 같다면 부분문자열을 이용해서 계속 비교를 해주었다. 탐색한 부분이 폭팔해야 되는 지점이면 i 인덱스를 올려주었고 새로운 단어를 만들게 되면 다시 while 룹을 반복해서 더 이상 폭팔이 안되는 구간까지 계속 돌려주었다.
그러나 결과는 TLE. 시간 초과가 되었다. 내가 쓴 코드를 가만히 계속 보다보니 이런식으로 하나씩 비교하는건 정말 안좋은 방법이라고 생각했다. 애초에 문자열의 길이가 백만이 되는데 폭팔되는 문자가 C4 이고 예시로 주는 문자열이 CCCCCCC4444444.. 정말로 많은 while 룹을 반복하게 되고 절대로 시간안에 못끝낼거같다는 판단이 나왔다.
그렇다면 가장 이상적인 케이스는 백만번의 룹을 단 한번에 끝내는 과정인데 솔직히 오늘 컨디션도 안좋았고 이미 이 문제에 꽤 많은 시간이 들어갔기때문에 답을 참고했었다.
그 결과, 내가 생각했던 로직과 그렇게 다른점은 없었고 그저 index를 활용한 단어 체킹만 할수있었다면, 또 폭팔되야 하는 지점을 그 자리에서 바로 폭팔해주고 계속 확인을 해줄수있었다면 한번에 for 룹안에 끝날수있었던 문제였다.
[v.size()-target.length() + j] 는 되게 간단한 계산 방법이였고 sliding window 같은 느낌으로 단어 하나씩 검색만 해주면 됐었다. 그리고 여기 있는 if 문 안에 substr을 써서 비교해줬어도 깔끔한 코드가 나왔을것만 같다. 되게 쉬운 문제였지만 TLE 가능성을 생각을 잘 못했었고 이렇게 원큐에 끝날수있는 문제를 무한 룹을 이용하려고 했던 생각이 큰 화가 됐던거같다. 컨디션이 좋았을때는 좀 더 신중한 모습으로 문제를 풀어야겠다.
배운점:
1. 문자열 검색을 위한 stack 응용 방법
2. 침착하게 풀어야한다.
