문제 링크:
https://leetcode.com/problems/longest-substring-without-repeating-characters/

문제 접근

이 문제는 Two Pointers 알고리즘을 이용해서 풀었다.
(Two Pointers 개념은 따로 정리해뒀다.)

문제의 목표는 입력받은 문자열에서 반복하지 않으면서 가장 긴 단어의 길이를 찾는 것이다.
나는 총 2가지의 방법으로 문제를 접근해봤다.
첫 번째 방법은 unordered_set을 이용해서 문제를 해결했고,
두 번째 방법은 정수형 배열을 이용해서 문제를 해결했다.

unordered_set 방법

unordered_set 을 사용한 이유

unordered_set 은 이름 그대로 값들이 정렬이 되지 않는 상태로 저장이 된다.
그리고 set 과 map 처럼 find, insert, erase 함수도 지원해주고, 그 속도는 O(1)으로 수행된다.
사실, 공부하고 있는 컨테이너라서 한번 사용해봤다...ㅎㅎ

pseudocode

1. 변수 생성
• 시작점과 끝점을 가리키는 포인터를 만든다.
• 시작점과 끝점 사이의 캐릭터들을 보관할 캐릭터형 unordered_set 을 만든다.
• 배열의 길이를 저장할 정수형 변수를 만든다.
2. 로직
• 시작점과 끝점이 문자열 길이보다 작은 경우에만 반복
• 끝점이 가리키는 캐릭터를 unordered_set에서 검색
• 만약, 검색이 안 된다면 캐릭터를 unordered_set 에 추가하고 최댓값 정의 후 끝점 한 칸 증가
• 검색이 된다면 시작점이 가리키는 캐릭터를 unordered_set 에서 삭제 후 시작점 한 칸 증가
• 최댓값을 리턴

#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만 연습하고,
내장 함수의 기능의 도움을 많이 받은 코드였다..ㅎ
역시 내장 함수 짱👍

정수형 배열 방법

정수형 배열을 사용한 이유

아직까지도 나에게 가장 익숙한 것은 기본 배열이다.
그리고 비록 문자열을 입력받지만, 알파벳도 아스키코드값을 가지고 있기 때문에 충분히 가능성 있다고 생각했다.

pseudocode

1. 변수 생성
• 시작점과 끝점을 가리키는 포인터를 만든다.
• 시작점과 끝점 사이의 캐릭터들을 보관할 정수형 배열을 만든다.
• 배열의 길이를 저장할 정수형 변수를 만든다.
2. 로직
• 문자열을 순환할 인덱스가 문자열의 길이보다 작은 경우에만 반복
• 배열 속 캐릭터의 아스키코드 값의 자리를 하나 증가 후 끝점 한 칸 증가
• 만약, 해당 캐릭터의 아스키코드 값의 자리가 1보다 크면 시작점의 아스키코드값의 자리를 1 감소
• 그리고 시작점을 한 칸 증가 후 끝점은 한 칸 감소
• 만약 끝점이 최대댓값보다 크면 끝점을 최댓값으로 정의
• 최댓값 리턴

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에 대한 개념은 어느 정도 자리 잡힌 것 같다. !
무~ ㅇㅑ 호!