오늘은 정말로 오래전에 나온 리트코드 문제이고 또 나도 굉장히 오래전에 풀어봤지만 잘 기억이 안나는 문제를 풀어보았다. 이 문제가 좀 어렵게 느껴지는 이유중 하나는 통과 해야하는 테스트케이스가 무려 987 개나 있다는 점이었다.
당연하게 무슨 이런 테스트 케이스가 있지 하는 문제들도 있었을테고 그렇기때문에 더 완벽하게 코드를 짜야하는 점도 있었다. 문제가 말하는 질문은 굉장히 심플한데 반복되지 않는 문자가 나오지 않을때까지 가장 긴 문자열의 길이를 리턴하면 되는 문제이다.
즉, abca 가 나올경우, a 가 중복되게 나오기 전인 abc 가 가장 긴 문자열이라고 생각하면 되는것이다.
여기서 가장 중요한거는, 중복되는 문자열을 확인할수있는 자료구조, 즉 Map 을 써야했던 부분이고, 가장 긴 문자열을 확인 할수있는 구간을 계산하기 편한 Two Pointer, 혹은 sliding window 가 필요했다.
이 코드는 굉장히 오래전에 어떤 유투브 강의를 보고 따라 적었던건데 그 당시에는 이해가 잘 안됐지만 지금 보니깐 정말 잘 썼구나 하는 정석적인 코드인거같다.
먼저 left 와 right 을 지정해주고 right 을 옯겨준다. 다만 여기서 Map 에서 이미 봤던 문자를 보게된경우에는 그 문자가 원래 있었던 위치를 left 로 지정해주고 최대 길이를 구하면 됐었다. 다만 여기서 이해가 안됐던 부분 중 하나는 hashMap[c] > left 였는데 이것은 left 포인터가 원래 있어야 하는 c 의 위치보다 더 앞섰을경우만 계산 하라는 뜻이었다.
abba 에서 b랑 a는 동시에 겹친다. 그리고 b가 중복이 되었을때는 right = 2 그리고 hashMap[b] 가 1 이기 때문에 최대값이 1이 되지만. 그 두번째 a가 중복 체크가 되었을때는 right = 3 이고 원래 있는 a 의 위치는 0 이기때문에 최대값이 3으로 잘못나온다. 그러므로 내가 현재 위치하고 있는 left의 값이 원래 문자의 위치보다 더 앞선다면 그 계산은 무시해주는게 맞다는 답이다.
배운점:
1. Two pointer 을 활용한 sliding window
2. 복잡하게 생각하기 않기
