(출처) https://leetcode.com/problems/longest-substring-without-repeating-characters/
원소가 중복되지 않게하면서 최대한 길게 원소를 쌓아라
해당 문제는 주어진 인풋 배열에서, 연속되면서 원소가 중복되지 않는 가장 긴 부분을 찾아 리턴하면 되는 문제이다. (사실 입력은 String이지만 배열이라고 생각해도 될 것 같다)
나는 포인터 P로 배열을 하나씩 탐색해가면서, 중복이 아닌 원소를 발견하면 큐에 자료를 등록하는 식으로 문제를 해결해보기로 했다.
이때 같은 원소가 큐에 중복적으로 저장되지 않도록 하기 위해 추가적인 검사 과정이 필요하다.
해당 기능을 구현하기 위해서 큐뿐만 아니라 map 자료구조에도 따로 원소를 등록해 주는 과정을 추가했다.
map을 이용하여(이진탐색트리) 자료의 중복여부를 빠르게 검사하고자 하는 전략이었다.
(사실 코드를 다 짜고 보니 Value 값은 딱히 필요 없어서 set을 쓰는 게 맞았던 것 같은데 귀찮아서 그냥 넘어갔다..)
구체적으로 말해보자면 포인터 p를 한 칸씩 이동시키면서 p가 가리키는 원소가 map에 아직 등록이 되지 않은 원소라면 map과 큐에 추가해 주는 식으로 작업을 진행하고, 만약 포인터가 가리키는 원소가 map에 등록이 되어있는 중복된 원소였다면 큐를 새롭게 갱신하는 식으로 작업을 진행했다.
큐를 새롭게 갱신하는 과정은 포인터 P가 가리키는 원소를 큐에서 꺼낼 때까지 계속 pop을 시키는 식으로 진행한다. 큐에서 중복된 원소를 찾아내어 제거하고 다시 새로운 p의 원소를 추가하는 방식이다. (pop을 시키면서 map에 등록된 자료도 동시에 삭제해야 한다)
그리고 위의 모든 과정이 다 끝났다면 현재 큐의 길이를 구해서 result와 비교한다.
(result는 큐의 최대 길이를 보관하고 있다)
만약 현재 큐의 길이가 result보다 더 크다면 result의 값을 갱신하고, 크지 않다면 그냥 그대로 다시 p를 한 칸 움직여준다.
이후 배열을 전부 순회했다면 최종적으로 result를 리턴하면 된다.
시간복잡도
시간복잡도는 포인터 p가 배열의 원소 n개를 전부 탐색하는 과정에서 n번의 반복이 소모된다. (외부루프)
그리고 각 반복마다 현재 포인터 p가 가르키는 원소가 중복을 일으키는 원소인지 아닌지 판단하는 작업을 실시하는데, 즉 map에서 특정 원소가 존재하는지 검사하는 작업이다. (내부루프)
이진검색트리에서 특정 자료를 탐색하는 것에는 O(log 총 원소의 개수) 의 시간복잡도가 소모되므로 그냥 내부루프의 시간복잡도는 O(log N) 이라고 해도 될 것 같다.
따라서 총 시간복잡도는 O(N * log N) 이 되고, N의 최대는 5만이므로 충분히 해당 로직으로 해결할 수 있다.
코드
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
int static lengthOfLongestSubstring(string s) {
int result = 0;
int p = 0;
queue<char> q;
map<char,int> m;
char ch;
while(p < s.size()) {
if(m.find(s[p]) != m.end() && m[s[p]] != 0) {
do{
ch = q.front();
q.pop();
m[ch]--;
}while(ch != s[p]);
}
m[s[p]] = 1;
q.push(s[p]);
int temp = q.size();
result = max(result, temp);
p++;
}
return result;
}
};
int main() {
int a = Solution::lengthOfLongestSubstring("pwwkew");
cout << a << endl;
}