[leetCode 3번] Longest Substring Without Repeating Characters (JAVA)

1. 문제

Longest Substring Without Repeating Characters - LeetCode

Longest Substring Without Repeating Characters - LeetCode

---

2. 문제 설명

    이 문제는 주어진 문자열에서 문자열을 탐색하는 것이다. 이 때 문자열에서 탐색하여 중복 없이 구성 된 문자열 중 가장 긴 길이를 찾는 것이다.

---

3. 소스 코드

public static int lengthOfLongestSubstring(String s) {
        int maxLength = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        Set<Character> sets = new HashSet<>();

        while (right < s.length()) {
            if (!sets.contains(s.charAt(right))) {
                sets.add(s.charAt(right));
                maxLength = Math.max(maxLength, sets.size());
                right++;
            } else {
                sets.remove(s.charAt(left));
                left++;
            }
        }

        return maxLength;
    }

---

4. 소스코드 해설

 

이 문제는 슬라이딩 윈도우와 Set을 활용하여 중복을 제거 하는 알고리즘을 사용 하였다.

 

left , right 포인터를 선언하여 윈도우를 만들어 순회 하고 

 

sets 는 중복이 없는 집합을 넣어줄 Set 함수이다.

 

만약 s.charAt(right) 가 sets 에 없다면 윈도우 에 문자를 추가하고 최대 길이 (maxLength) 에 업데이트 후 right 를 증가 시킨다.

 

만약 중복 문자가 존재 하면 윈도우에서 가장 왼쪽을 제거 하 left를증 가시킨다 이러한 과정을 right 가 문자열 끝까지 도착 할때 까지 반복 한다.

 

예시 )

 

문자열 : "abcabcbb" 

 

1. left = 0 , right = 0 -> sets = {}

 

2. left = 0 , right = 1 -> sets= {'a'}

 

3. left = 0 , right = 2 ->  sets= {'a','b'}

 

4. left = 1 , right = 2 -> sets = {'b'} 

 

5. left = 1 , right = 3 -> sets = {'b' , 'c' }

 

6. left = 3 , right = 5  -> sets = {'c','a','b'}  -> return Maxlength = 3 을 반환

---

5. 회고

 

이 문제를 접했을때 간단하게 풀 줄 알았다.... 처음 생각 했던 슬라이딩 윈도우는 중복을 어떻게 제거해야할 지를 고민을 많이 했던 것 같다. 그 이전 값을 가지고 현재값과 비교하여 삭제 하는 방법? 아니면 Map 을이용하여 키값으로 체크? 라는 방법으로 여러 시도를 하였을때 많은 시도 끝에 결국... 구글링을 해보 았다. 다양한 방법들이 존재 하였지만 여태 나와 제일 비슷 하게 생각하고 결과도 원하는 방법은 Set을 사용하는 방법이였다는것을 알았다 Set은 중복을 제거해준다는 것을 알고 있었지만 이 문제에서 활용해야겠다는 생각은 미처 못하고 있었다.