투 포인터, 슬라이싱 윈도우

사용 전략?

 

일단은, For문으로 생각해본다. 

for문으로 생각하면 이중, 삼중이 되어 시간 복잡도가 1억이 넘는 경우가 생기는데, 이럴때 생각해볼 방안이다.

 

투포인터의 핵심은

기존 정보를 저장해놓고, start, end index를 조정하여 특정 원소만 빼고 더한다는 것이다.

투포인터의 시간복잡도는 O(N)이다.

하지만 아무렇게나 짠다고 O(N)이 되어 주는 것은 아니고,

기존 정보를 저장해놓고 END는 목표 (보통 WHILE문 안에 END<N으로 표현)치까지 가고,

START는 그 이후에 해당 INDEX를 쫓아가게 구현해야 한다.

 

그리고, 한 작업 중에 START나 END 모두 같은 방향으로 움직여야 한다.
그래야 O(2*N = N)이 나온다.

핵심 마지막은, 그러한 포인터들이 초기화되어선 안된다는 것. 
END가 3일때 START가 다 돌고 0으로 돌아온다면, O(N^2)가 되어버린다.

 

언제 적용할 지 고민할까

N이 굉장히 커서, for문 만으론 활용하기 힘들 때.

이 관점에서 보았을 때 백트래킹이나 재귀와 혼동되기도 하지만, 시간 복잡도를 계산해서 써먹자.