🖥️ 시작하며
일단 있는 그대로 풀이를 시작하면, 파이썬으로는 슬라이싱으로 굉장히 쉽게 할 수 있다.
from typing import List class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 for i in range(len(s)): # 길이를 저장할 임시 변수 tmpres = 0 # substring에 문자가 더 들어가는지 확인 for j in range(i, len(s)): if s[j] in s[i:j]: break tmpres += 1 res = max(res, tmpres) return res s = Solution() print(s.lengthOfLongestSubstring("pwwkew"))
하지만 시간이 너무 오래 걸려서.. 더 좋은 풀이가 있나 싶어 찾아보다, 인상적인 풀이를 보게 되었다.
역시 이런 문제는 집합을 사용하는 게 국룰인 것 같다.
from typing import List class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 visit = set() left = 0 # 왼쪽 idx # 오른쪽 idx부터 시작 for right in range(len(s)): # visit에 있다면, visit에서 삭제하고 left 인덱스 증가 # left와 right를 이용해 전체 길이 구함 while s[right] in visit: visit.remove(s[left]) left += 1 # visit에 문자 추가 visit.add(s[right]) res = max(res, right - left + 1) return res s = Solution() print(s.lengthOfLongestSubstring("pwwkew"))
예를 들어
s = "pwwkew"
의 경우:- 문자
p
를 처리할 때visit = {'p'}
,res = 1
.
- 문자
w
를 처리할 때visit = {'p', 'w'}
,res = 2
.
- 또 다른
w
를 만나면visit
에서p
를 제거하고l
을 이동,visit = {'w'}
,res = 2
.
- 문자
k
를 처리할 때visit = {'w', 'k'}
,res = 2
.
- 문자
e
를 처리할 때visit = {'w', 'k', 'e'}
,res = 3
.
- 마지막으로
w
를 처리할 때visit
에서w
이전 문자를 제거하고, 최종적으로visit = {'k', 'e', 'w'}
,res = 3
.
⚙️ Python
from typing import List class Solution: def lengthOfLongestSubstring(self, s: str) -> int: res = 0 visit = set() left = 0 # 왼쪽 idx # 오른쪽 idx부터 시작 for right in range(len(s)): # visit에 있다면, visit에서 삭제하고 left 인덱스 증가 # left와 right를 이용해 전체 길이 구함 while s[right] in visit: visit.remove(s[left]) left += 1 # visit에 문자 추가 visit.add(s[right]) res = max(res, right - left + 1) return res s = Solution() print(s.lengthOfLongestSubstring("pwwkew"))
⚙️ C++
#include <iostream> #include <set> #include <string> using namespace std; class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0; set<char> visit; int left = 0; for (int right = 0; right < s.length(); ++right) { while (visit.find(s[right]) != visit.end()) { visit.erase(s[left]); left++; } visit.insert(s[right]); res = max(res, right - left + 1); } return res; } }; int main() { Solution solution; string test = "pwwkew"; cout << solution.lengthOfLongestSubstring(test) << endl; return 0; }
📌 소감
아.. 문자열 만지는 문제는 언제나 어려운 것 같다.
댓글