[LeetCode] 3. Longest Substring Without Repeating Characters (C++)

Longest Substring Without Repeating Characters - LeetCode

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

---

중간고사 기간이지만 오랜만에 알고리즘 문제를 풀었다. 역시 시험 기간에는 시험이랑 관련 없는 모든 딴짓이 재미있다. 저번 주에 경험 삼아 코테를 봤었는데 문자열에 약하다고 느꼈다. 그래서 문자열 처리 위주로 문제를 풀어보기로 했다. 문자열 처리 한정으로 파이썬을 익히는 것도 나쁘지 않을 것 같다.

 

이 문제는 주어진 문자열에서 중복이 없는 문자들로 가장 긴 substring의 길이를 구하는 문제였다. 처음 봤을 때에는 DP인가 싶었지만 그렇다고 하기엔 들어오는 문자의 종류가 너무 많다는 생각이 들었다. 그래서 조금 더 생각해보다 큐가 떠올랐다. 거기다가 나름 그리디라고 해야 되나...? 아무튼 문자열 인덱스를 하나씩 증가시키면서 문자열에 이미 해당 문자가 들어있는지 검사한다. 없으면 push 하고 있으면 해당 문자가 빠질 때까지 pop 한다.

 

그런데 중복 검사를 하기 위해서는 또 다른 자료 구조가 필요했다. 배열로 하기에는 들어오는 문자들을 어떻게 인덱싱을 해야 될지 모르겠어서 set을 사용하기로 했다. 아스키코드를 모두 외우고 있었으면 배열로 할 수도 있었을 것 같다. 그런데 set의 메서드를 잘 몰라서 찾아봐야 했다. 지금까진 그냥 나 혼자 문제를 푸는 거라서 그때그때 찾아보면서 했었는데 코테를 보니 이런 식으로는 안될 것 같았다. 최대한 안 찾아보고 해 봐야겠다. 

 

아무튼 문제를 풀긴 풀었는데 백분위가 맘에 들지 않았다. 생각해보니 set을 사용하는 시점에서 큐를 사용하지 않아도 될 것 같았다. 또 배열을 사용해서 푸신 분도 계셨다. leetcode가 코드 리뷰하기는 진짜 좋은 사이트인 것 같다.

 

 

후기)

파이썬을 진짜 써봐야 하나 싶다.