LeetCode in C# 3. Longest Substring Without Repeating Characters

 

문제 요약

같은 문자가 반복되지 않는 가장 긴 문자열의 길이를 구해라

 

문제 핵심 (주관적)

1. 반복문으로 문자끼리 전부 비교하는게 가장 쉬운 해결책이겠지만, 조금 더 시간 복잡도를 낮출 수 있는 방법 모색하기.

2. 공백 예외처리, 공백문자가 나와도 문자가 이어짐으로 판단해야함.

3. 순차적이 아니라, 전체적으로 봤을 때, 가장 긴 숫자를 선정해야함.

 

풀이방법 (1차)

반복문을 사용하는 방법이 가장 먼저 떠올라서 구현해봤습니다. 탐색 알고리즘을 만들어서 해결하면, 분명 시간 복잡도를 낮출 수 있을 것 같다는 생각이 들었지만, 방법이 떠오르지 않아서 문제 해결에 포커스를 맞췄습니다. 

 

풀이 핵심은 리스트를 활용해서 중복되지 않은 문자들을 추가하고, 만약 중복된 문자가 있다면 전부 비우고 다시 추가하는 구조로 문제를 해결했습니다.

 

시간 복잡도 : O(n^2)

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int max = 0; //최장 길이
        List<char> checkList = new List<char>(); //문자 확인용

        for(int i =0; i< s.Length; i++)
        {
            int curLen = 0; //현재 길이
            for(int j = i; j< s.Length; j++)
            {
                //중복된 값이 존재할 경우
                if(checkList.Contains(s[j]))
                {
                    checkList.Clear(); //리스트 비우기
                    break;
                }
                
                curLen++;
                checkList.Add(s[j]);
            }

            max = max > curLen ? max : curLen; //이전 값과 길이 비교
            checkList.Clear();
        }
        return max;
    }
}

 

 

풀이방법 (2차)

풀이의 핵심은 HashSet을 사용해 요소 탐색에 걸리는 시간을 줄이는 것과, 좌우로 포인터를 위치시켜, 반복하지 않아도 해당 포인터로 문자에 접근하여 문장의 길이를 판단할 수 있게 하는 구조를 만드는 것이였습니다. 

 

1. 반복이 될때마다, 중복값을 확인함

2. 중복된 값이 아니라면, HashSet에 추가, R포인터 우측으로 한칸 이동, max값 갱신

3. 중복된 값이라면, HashSet의 L포인터의 문자 제거, L포인터 한칸 옮김

 

시간 복잡도 : O(n)

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int left = 0; //왼쪽 포인터
        int right = 0; //오른쪽 포인터
        int maxLength = 0; //문자열의 최장 길이
        HashSet<char> charSet = new();

        while(right < s.Length) 
        {
            //중복된 값이 있는지
            if(!charSet.Contains(s[right]))
            {
                 charSet.Add(s[right]);
                 right++;
                 maxLength = Math.Max(maxLength,right - left);
            }
            else
            {
                charSet.Remove(s[left]);
                left++;
            }
        }
        return maxLength;
    }
}