리트코드 3. Longest Substring Without Repeating Characters JAVA

문제

문제 해석

간단하게 문자열에서 중복되는 단어 없이 얼마나 긴 문자열을 만들어낼 수 있는가?의 문제다.

if문을 통한 해결

if문들을 활용해서 조건별 분기를 진행하는 코드다.
추가적인 자료구조를 활용하지 않고 문제를 해결 할 수 있기 때문에 공간복잡도는 상당히 낮을 것이라고 예상된다.

수도코드

        int max = 1;
        int k = 0;

        for(int i = 0; i < s.length();i++){
            //왼쪽 끝과 걸렸을 때 걸렸을 때
            for(int j = k ; j < i ; j++){
                if(s.charAt(j) == s.charAt(i))
                    k == j + 1;
                    break;
            } 
            max = Math.max(max, i - k + 1);
        }

수도 코드를 설명하자면 k는 마지막으로 중복되지 않는 값을 의미한ㄷ.
2번째 for문은 중복 여부를 검증하는 루프다.
중복이 발생된다면 해당 인덱스인 j + 1을 k에 저장한다.
이 후 기존의 Max와 비교해 더 큰 값을 입력한다.

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int k = 0;

        for(int i = 0; i < s.length();i++){
            for(int j = k ; j < i ; j++){
                if(s.charAt(j) == s.charAt(i)){
                    k = j + 1;
                    break;
                }    
            } 
            max = Math.max(max, i - k + 1);
        }
        return max;
    }
}

위의 수도 코드 설명처럼 나는 추가적인 자료구조를 사용하지 않고 문제를 해결하기 위해서 for문과 charAt()을 활용했다.
또한 2번째 for문에 break를 둬서 미리 발견하게 될 경우 불필요한 로직을 수행하지 않고 작업을 끝낼 수 있는 장치를 만들어뒀다.
nlogn 의 시간 복잡도가 발생할 것이라고 생각이든다.

실제 속도 또한 준수하게 나오고 있다.

슬라이싱 윈도우에서 가장 중요한 것은 일단 창을 만들어 연산의 크기를 줄여주는 것이 중요한 것 같다.
내 로직도 보면 일단 창의 크기를제어하기 위한 변수를 포함하고 있다.

솔루션 확인 ( Set을 활용한 방법)

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        Set<Character> charSet = new HashSet<>();
        int left = 0;

        for (int right = 0; right < n; right++) {
            if (!charSet.contains(s.charAt(right))) {
                charSet.add(s.charAt(right));
                maxLength = Math.max(maxLength, right - left + 1);
            } else {
                while (charSet.contains(s.charAt(right))) {
                    charSet.remove(s.charAt(left));
                    left++;
                }
                charSet.add(s.charAt(right));
            }
        }

        return maxLength;
    }
}

자료구조 Set을 사용해서 푸는 문제다.
내 생각에 자료구조를 사용하는 가장 큰 이유는 contains라는 메서드를 활용하기 위한 것이라고 생각된다.

해당 코드의 속도를 내 코드의 속도와 비교해보자