[Grind75-LeetCode] Longest Substring Without Repeating Characters JAVA

반응형

728x90

[Grind75-LeetCode] Longest Substring Without Repeating Characters - Medium

---

접근

• Set
• 슬라이딩 윈도우
• 슬라이딩 윈도우 성능 향상

---

풀이

문자열 내 부분 문자열 중 가장 긴 부분 문자열의 길이를 구하는 문제이다. 겹치는 문자 없이 부분 문자열을 이루어야 하는 조건이 있고 단순한 Set을 이용한 방법과 Map을 이용한 슬라이딩 윈도우 알고리즘 그리고 Map 대신 배열을 사용하여 성능을 향상 시킨 슬라이딩 윈도우 순서로 진행할 예정이다.

 

우선 Set을 사용한 방법이다. 가장 직관적이고 쉬운 방법으로 각 인덱스에서 2중으로 반복문을 돌며 Set에 추가해 이미 존재하는 원소라면 반복을 중단하고 길이를 반환하여 최댓값을 구하는 방식이다. 가장 간단하고 쉬운 방법이지만 2중 반복문을 사용한다는 점과 Set을 매번 새로 생성하던가 Clear()를 통해 비워줘야 하기에 처참한 성능을 자랑했다.

    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Set<Character> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            int count = 0;

            for (int j = i; j < s.length(); j++) {
                if (set.contains(s.charAt(j))) {
                    set.clear();
                    break;
                }

                set.add(s.charAt(j));
                count++;
            }

            maxLength = Math.max(maxLength, count);
        }

        return maxLength;
    }

Set을 매번 clear() 하는 방식으로 구현된 코드이고 Set에 존재 여부를 판단해 진행되는 방법이다.

Set을 이용한 방식

실행시간 82ms로 처참한 성능을 자랑했고 Set을 두 번째 for문 아래에서 매번 생성하는 경우 100ms가 넘는 실행 속도를 보여줬다. 

---

슬라이딩 윈도우  (Sliding Window)

슬라이딩 윈도우는 예전에 백준의 과일 탕후루 문제를 풀 때 사용했던 알고리즘으로 이 문제에도 사용할 수 있는 방법이다.

2024.09.03 - [알고리즘/코딩테스트-백준] - [백준] 과일 탕후루 JAVA

[백준] 과일 탕후루 JAVA

슬라이딩 윈도우는 시작과 끝 양쪽 포인터를 옮겨가며 최대 길이를 찾는 방법인데 Map을 통해 각 문자의 마지막 인덱스를 Map에 저장해 두고 겹치는 문자가 나올 경우 포인터를 그 문자 다음으로 옮겨 가며 진행하게 된다.

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> indexMap = new HashMap<>();
        int maxLength = 0;
        int start = 0; 
        
        for (int end = 0; end < s.length(); end++) {
            char current = s.charAt(end);
            
            if (indexMap.containsKey(current) && indexMap.get(current) >= start) {
                start = indexMap.get(current) + 1;
            }
            
            indexMap.put(current, end);
            
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }

Map과 시작 포인터를 선언하고 끝 포인터는 for문에 의해 관리된다. 현재 문자가 Map에 존재하지 않는 경우 Map에 현재 문자와 인덱스를 저장한다. 만약 Map에 현재 문자와 같은 문자가 존재하고 그 문자의 index가 현재 시작 포인터보다 크거나 같다면 시작 포인터를 해당 문자가 있던 인덱스 다음 칸으로 옮긴다. 예를 들어 문자열이 "abcab"라면 abc까지는 Map 내에 존재하지 않아 각 인덱스 별로 a:0, b:1, c:2 형태로 저장이 될 것이고 3번 인덱스의 a 차례가 되었을 때 이미 Map 내부에 0번 인덱스에 a가 있었다는 내용이 존재한다. 현재 시작 포인터는 0이고 a의 인덱스 또한 0으로 시작 포인터와 끝 포인터 내, 즉 부분 문자열 내부에 a라는 문자가 존재하고 있다는 뜻이기 때문에 시작 인덱스를 조정해 앞에 있던 a를 부분 문자열 밖으로 내보내는 것이다. 

s = "abcab"

start = 0, end = 2 current = 'c'
Map = [a:0], [b:1], [c:2]
substring = "'abc'ab"

start = 0, end = 3 current = 'a'
Map.containsKey('a') = true && Map.get('a'){0} >= start{0} = true
substring = "a'bca'b"
Map = [b:1], [c:2], [a:3]

---

성능 개선

다른 사람의 풀이를 봐도 거의 대부분 맵을 통한 슬라이딩 윈도우를 사용해 푼 것을 볼 수 있었는데 결과에선 이 방법 보다 한 단계 더 좋은 성능의 코드가 존재했다. 현재 Map을 사용한 코드는 5ms의 실행 시간을 가졌다.

Map을 사용한 슬라이딩 윈도우

2ms 실행 시간을 가진 코드가 존재하는 걸 볼 수 있는데 이미 충분한 성능인지라 동일한 알고리즘을 Map을 사용하지 않고 배열 같은 자료구조를 사용해 성능을 올린 게 아닌가 싶어 GPT에게 성능 개선 방법에 대해 물어봤더니 배열을 사용해 개선된 코드를 보여주었다.

    public int lengthOfLongestSubstring(String s) {
        int[] indexArr = new int[128];
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char current = s.charAt(end);
            start = Math.max(start, indexArr[current]); 
            
            indexArr[current] = end + 1; 
            
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }

위의 코드는 Map 대신 배열을 사용해 개선한 코드이다. 문자의 인덱스 저장 방식을 배열을 통해 나타내었는데 크기가 128인 이유는 ASCII 코드 값에 맞추기 위해 128로 선언되었으며 현재 문제는 문자만을 다루다 보니 소문자인 65~90 번지와 대문자인 97~122 번지 인덱스만을 사용한다고 보면 된다. 각 문자의 아스키 코드에 해당하는 인덱스에 시작 포인터를 조정할 위치 값을 넣어 매번 시작 포인터와 해당 문자의 인덱스 내부 값 중 큰 값의 위치로 포인터를 이동하게 된다. 큰 값을 기준으로 결정되기 때문에 기존 시작 포인터의 값 보다 작은 값일 경우 부분 문자열 밖으로 포인터가 변경되지 않고 시작 포인터 보다 큰 값일 경우 부분 문자열 내부로 판단해 시작 포인터를 변경하게 된다. 

배열을 사용한 슬라이딩 윈도우

Map에서 배열로 자료구조를 변경하여 5ms -> 2ms 로 성능이 개선되었다.

	Set(매번 생성)	Set(매번 Clear)	슬라이딩 윈도우(Map)	슬라이딩 윈도우(배열)
실행 시간	111 ms	82 ms	5 ms	2 ms
메모리 사용	45.3 MB	45.03 MB	44.43 MB	42.92 MB

전체적으로 메모리 사용과 실행 시간이 점차 개선되는 모습을 볼 수 있다.

---

전체 코드

Set

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Set<Character> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            int count = 0;

            for (int j = i; j < s.length(); j++) {
                if (set.contains(s.charAt(j))) {
                    set.clear();
                    break;
                }

                set.add(s.charAt(j));
                count++;
            }

            maxLength = Math.max(maxLength, count);
        }

        return maxLength;
    }
}

 

슬라이딩 윈도우 (Map)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> indexMap = new HashMap<>();
        int maxLength = 0;
        int start = 0; 
        
        for (int end = 0; end < s.length(); end++) {
            char current = s.charAt(end);
            
            if (indexMap.containsKey(current) && indexMap.get(current) >= start) {
                start = indexMap.get(current) + 1;
            }
            
            indexMap.put(current, end);
            
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

 

슬라이딩 윈도우 성능 개선 (배열)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] indexArr = new int[128];
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char current = s.charAt(end);
            start = Math.max(start, indexArr[current]); 
            
            indexArr[current] = end + 1; 
            
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}