사지방에서 문제를 풀면서 즐겁게 했던 문제중 하나인거같다. 이번에도 어김없이 백트래킹 문제를 골랐고 s라는 스트링이 주어질때 중복되는 캐릭터가 없는 가장 긴 substring 으로 최대의 숫자로 분할을 하고 횟수를 리턴하면 되는문제이다.
가장 먼저 생각했던 방법은 dfs 방식이었고 가장 밑에 코맨트로 어떤식으로 접근할지를 미리 생각해놨었다. 여기서 추가적으로 필요했던건 map 이었고 내가 현재 만든 substring 이 중복이 안되어있는 유니크한 스트링인지를 확인하기 위해 필요했다.
이 문제를 풀면서 가장 중요하다고 생각했던건 index 라는 내가 고른 임의에 숫자와 for 룹안에서 돌아가는 i 의 차이였다. 예전만 해도 백트래킹의 원리를 잘 몰랐을때는 index 의 존재 이유를 잘 몰랐고 index 와 i 이 차이가 모호했지만 이 문제를 통해서 더욱 자신감이 올랐다.
dfs() 부분에서 처음에 i + (check.length()) 를 했을때 원하는 답이 안나왔는데 그건 내가 i에다가 더했기 때문이었고 곧바로 index로 바꾸자마자 내가 원하는 답이 나왔다. check.length() 를 더해준 이유에는 맵에서 이미 카운트가 된 캐릭터가있으면 지속적으로 처음 본 스트링이 나올때까지 더 해줘야했기 때문이다. 마지막으로 dfs 에서 콜이 돌아오게되면 map에서 내가 본 캐릭터를 지우는걸로 완벽한 코드가 됐다.
배운점:
1. index 와 i 의 차이
2. 백트래킹 후에 돌아오는 과정에 대한 생각
성장하는 사람