Leetcode - 3. Longest SubString Without Repeating Characters

leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

 

Answer.

슬라이딩 윈도우 방식을 이용했다.

left에서 right까지 훑는 dummy라는 변수를 만들고

dummy의 값이 right와 같다면 dummy+1의 값으로 left로 이동시키는 방식으로 풀었다.

 

처음에는 16번째 라인을 left = right로 했었는데

오류가 계속 발생하여 생각을 해보니 슬라이딩의 왼쪽인 left가 '중복된 값이 발생한 다음 칸으로 이동'해야 한다는 걸 알게 되어 left = dummy + 1이라는 값으로 지정해줬다.

 

다만 다소 많은 계산으로 인해 속도가 조금 느리게 나왔었다.

 

첫번째 답 연산속도

 

그래서 다른 사람들은 어찌 해결했나 봤더니 해시맵을 사용해서 O(n)의 속도로 처리를 했었다. 

 

코드는 다음과 같다.

 

 

해시맵에 right의 인덱스 값과 해당하는 char값을 저장하고

 

만약 중복된 것이 나온다면 

현재 left값과 해시맵상의 값에서 + 1을 한 값(중복된 값의 다음값) 비교해 더 큰 것을 left로 설정하는 식이다. 

 

다른 사람들은 이와 같은 방법으로 속도를 끌어올렸었고 다음과 같은 결과가 나왔다.