Leetcode 3번 문제 풀이

개요

Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다.

 

문제 : 3. Longest Substring Without Repeating Characters

문자열내에서 중복이 없는 가장 긴 문자열의 길이를 반환해야 함.

 

풀이1 : Brute force

설명

Brute force(무차별 대입) 방식으로 풀 경우, 주어진 문자열 내 모든 문자들을 검사하여 풀 수 있다. 각각의 문자별로 루프를 돌아서 가장 긴 substring의 길이를 반환한다.

 

구체적으로는 다음과 같다.

 

• 전체 문자열 길이만큼 루프를 돌면서 조건에 따라 임시 문자열에 각 문자를 대입한다
  • 조건 1 : 만약 임시 문자열이 비어 있으면 최초 문자를 대입한다
  • 조건 2 : 만약 특정 문자와 임시 문자열을 중복 체크하여 중복이 아니면 임시 문자열에 대입한다
    (카운팅 넘버를 사용하여 중복체크 카운팅 숫자와 임시 문자열 길이가 같으면 그 때 대입함)
  • 조건 3 : 만약 중복 체크시 중복이면 임시 문자열을 빈 문자열로 초기화 시킨다
  • 루프가 종료되면 중복없는 임시문자열의 길이를 저장한다
• 위 루프를 전체 문자열내 각각의 문자마다 반복을 한다

 

코드

 

이 경우 시간복잡도는 O(n^3)가 나온다. 그러므로 정말 긴 문자열이 나오면 계산시간이 엄청 걸리기 때문에 모든 테스트를 통과할 수 있는 적합한 해결책은 아니다.

 

풀이2 : Sliding window

설명

무차별 대입보다 효율적으로 풀어서 시간 복잡도를 줄이는 것이 필요하다.

무차별 대입의 문제점은 매 substring마다 반복적으로 검사를 하는 것이다.

ex) 만약 문자열의 범위가 i 부터 j 까지라면 i 부터 j-1 까지 검사를 한다. 근데 이 후 i+1 부터 j-1 까지 검사를 하게 되면서 이미 검사한 범위를 또 지나가는 식으로 비효율적으로 동작한다.

 

우리가 해야할 것은 i 부터 j-1 까지 검사를 했을 때 다음 검사 범위는 j에서부터 시작하여 검사범위를 늘려가게 하면 된다.

 

이제 Sliding window(슬라이딩 윈도우) 를 이용한 풀이법을 알아본다.

 

슬라이딩 윈도우는 대략적으로 네트워크상에서 큰 용량의 데이터를 전송할 때 한꺼번에 다 보내지 않고 여러차례 나눠서 보내는 기법인데, 전체 데이터 중 프레임에 들어갈 만큼의 데이터만 넣고 이들을 하나씩 전송한다. 전송 완료하면 프레임을 옆으로 이동시켜서 전체 데이터를 보내는 식이다.

 

문제에 적용하면 다음과 같다

• 맨 처음 인덱스로부터 문자열 끝까지 루프를 돈다. 이 때 window (=substring) 의 범위를 지정하는 i, j 인덱스를 사용한다. (i = 어떤 substring의 시작 인덱스, j = 어떤 substring의 끝 인덱스. 두 인덱스는 처음 문자에서 동일하게 시작)
  
  • 만약 j 인덱스 위치의 문자가 중복이 아니라면 Set (자료구조) 에 문자를 저장하고 j 를 +1씩 늘려간다
    • Set을 사용하는 이유 : 무차별 대입방법에서 했던 것처럼 중복 확인을 위해 이중 루프를 돌며 스캔을 하면 O(n^2) 의 시간복잡도를 가지게 됨. 대신 Hashset 을 사용하면 O(1) 의 시간복잡도만에 만에 중복 검사를 할 수 있음
    • 이 때 j 와 i 인덱스의 차이 값으로 최대 길이를 구한다
      (이 때의 set의 size를 구하여도 정답이 된다)
  • 만약 중복이라면 Set 자료구조에서 i 인덱스 위치의 값을 삭제하고 i 인덱스를 증가시킨다

 

코드

 

이 때 시간 복잡도는 O(n) 가 되고 무차별 대입보다 훨씬 나은 성능을 보인다.

 

소감

window 기법에 착안하여 알고리즘을 고안해낸 것이 기발하방법들을 보며 많이 배울 수 있었다. 해당 방법이 생각날 뻔도 했지만 이미 문제 통과를 하기 위해 머리를 다 써서 더 나은 방법을 고안하지 못했다. 솔루션이 영어라서 해석하여 이해하는데 시간이 걸렸다. 그러나 이렇게 시간을 들여 제대로 이해를 한다면 머리에 잘 남게 되므로 수확있는 과정이라 생각된다.