해시셋

문제 설명 Longest Substring Without Repeating Characters - LeetCode 주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring) 의 길이를 반환하는 문제입니다. ✅ 부분 문자열(Substring) 조건: 연속된 문자만 포함해야 함 (순서를 바꾸면 안 됨) 중복 문자가 없어야 함 최대 길이를 반환 해설 1️⃣ 브루트포스 (O(N²)) - 비효율적 모든 가능한 부분 문자열을 생성하여 중복이 없는지 검사 → O(N²) 비효율적이므로 사용하지 않음 2️⃣ 투 포인터 + 해시셋 (슬라이딩 윈도우, O(N)) [추천] 해시셋(Set) 을 사용하여 중복 여부를 빠르게 검사 두 개의 포인터 (left, right) 를 사용하여 윈도우 크기를 조절 시간 복잡도: O(N) (각 문자를 한 번씩만 처리) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def lengthOfLongestSubstring(s: str) -> int: char_set = set() # 중복 문자를 빠르게 찾기 위한 해시셋 left = 0 # 윈도우의 왼쪽 포인터 max_length = 0 # 최대 길이 저장 for right in range(len(s)): # 오른쪽 포인터 이동 while s[right] in char_set: # 중복 문자가 있으면 왼쪽 포인터 이동 char_set.remove(s[left]) left += 1 char_set.add(s[right]) # 새로운 문자 추가 max_length = max(max_length, right - left + 1) # 최대 길이 갱신 return max_length Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var lengthOfLongestSubstring = function(s) { let charSet = new Set(); // 중복 확인을 위한 해시셋 let left = 0; // 윈도우의 왼쪽 포인터 let maxLength = 0; // 최대 길이 저장 for (let right = 0; right < s.length; right++) { // 오른쪽 포인터 이동 while (charSet.has(s[right])) { // 중복 발생 시 왼쪽 포인터 이동 charSet.delete(s[left]); left++; } charSet.add(s[right]); // 새로운 문자 추가 maxLength = Math.max(maxLength, right - left + 1); // 최대 길이 갱신 } return maxLength; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...