문제 링크:
https://leetcode.com/problems/longest-substring-without-repeating-characters/
이 문제는 Two Pointers 알고리즘을 이용해서 풀었다.
(Two Pointers 개념은 따로 정리해뒀다.)
문제의 목표는 입력받은 문자열에서 반복하지 않으면서 가장 긴 단어의 길이를 찾는 것이다.
나는 총 2가지의 방법으로 문제를 접근해봤다.
첫 번째 방법은 unordered_set을 이용해서 문제를 해결했고,
두 번째 방법은 정수형 배열을 이용해서 문제를 해결했다.
unordered_set 은 이름 그대로 값들이 정렬이 되지 않는 상태로 저장이 된다.
그리고 set 과 map 처럼 find, insert, erase 함수도 지원해주고, 그 속도는 O(1)으로 수행된다.
사실, 공부하고 있는 컨테이너라서 한번 사용해봤다...ㅎㅎ
#include <iostream>
#include <string>
#include <unordered_set>
int lengthOfLongestSubstring(std::string s) {
unordered_set<char> arr;
int result = 0;
int left = 0;
int right = 0;
while (left < s.size() && right < s.size()) {
if (arr.find(s[right]) == arr.end()) { // find함수는 해당 값을 찾지 못하면 end를 리턴한다.
arr.insert(s[right]);
result = max(result, right - left + 1);
right++;
}
else {
arr.erase(s[left]);
left++;
}
}
return result;
}
비록 unordered_set 을 사용해보겠다는 패기로 사용했지만, 결국 Two Pointer만 연습하고,
내장 함수의 기능의 도움을 많이 받은 코드였다..ㅎ
역시 내장 함수 짱👍
아직까지도 나에게 가장 익숙한 것은 기본 배열이다.
그리고 비록 문자열을 입력받지만, 알파벳도 아스키코드값을 가지고 있기 때문에 충분히 가능성 있다고 생각했다.
int lengthOfLongestSubstring(std::string s) {
int arr[125] = {0};
int max = 0;
int left = 0;
int right = 0;
for (int i = 0; i < s.size(); i++) {
arr[int(s[i])]++; // 아스키코드 값의 자리를 1 증가
right++; // 끝점을 한 칸 이동
while (arr[int(s[i])] > 1) { // 반복되는 캐릭터를 찾았다는 의미
arr[s[left]]--;
left++;
right--; // 최대값을 정의하기 위해서 1 감소
}
if (right > max)
max = right;
}
return max;
}
비록 unodered_set 을 사용했던 코드보다 런타임 속도나 메모리 사용량에서 좋은 결과를 보여줬지만,
코드를 구현하는데 몇 번의 시행착오를 겪었다. 특히 반복되는 캐릭터를 찾은 조건에서 while을 써야 하는 이유를 찾는데 오래 걸렸다.
while 을 쓰는 이유는 중복된 캐릭터가 시작점이 아닌 중간에 있는 경우가 있을 수도 있기 때문이다.
그리고 배열의 크기는 소문자 z의 아스키코드 값보다 조금 더 여유 있게 줬다. 참고로 z의 아스키코드값은 122이다.
사실 나는 아직 알고리즘 문제를 많이 풀어본 게 아니기 때문에, 런타임 속도와 메모리 사용량을 신경 쓰면서
문제를 푸는게 익숙하지 않다.. 예발자,,,ㅠ
그리고 시간 복잡도도 신경 쓰면서 하기에는 아직 너무 어렵다..
그래서 그냥 Two Pointers의 개념을 이해하고 문제를 풀어나가는데 집중했었다.
그리고 여러 방법을 사용하면서 푸는 것도 연습해봤다.
계속 문제를 풀면서 런타임에 걸려도 보고 메모리에도 걸려보면서 계속 경험을 쌓아야 할 것 같다.
그래도 Two Pointers에 대한 개념은 어느 정도 자리 잡힌 것 같다. !
무~ ㅇㅑ 호!