오늘도 연습해보는 sliding window 문제이다. 투포인터 형식의 문제는 이제 슬슬 많이 풀다보니 익숙해지는듯 하면서도 문제 유형이 조금씩 바뀐다면 아직도 헷갈리는 문제인거같다. 이번 문제는 타겟인 k 숫자보다 낮은 벡터안에 연속되는 작은 subarray의 숫자들을 찾는 문제이다.
가장 핵심 포인트는 i와j가 같은 시작점에서 시작하여 sum이라는 변수를 유지하며 j를 증가시키면서 숫자를 늘리고 sum이 k와 같거나 커졌을때는 i를 움직이며 찾는 범위를 줄이는것이다. 단순한 이중 for 루프로는 타임 에러가 나오기 때문에 O(n) 접근 방식으로 푸는 문제이다.
처음 썼던 너무 바보같았던 코드..테스트 케이스를 모두 통과하지 못했고 계속 고민하게 만든 문제였다. 여기서 내가 바보 같았던건 i 인덱스를 한칸씩만 움직이려했었던것. 윈도우의 범위를 원하는 만큼 줄이지 못했고 cnt 변수를 특정 조건안에서 하나씩만 올리려고 했었기에 이 코드는 망했다고 생각한다. 이 전에 풀었던 보석 문제를 자꾸 인식하다보니깐 이런 이상한 코드가 나온거같다.
다른사람의 코드를 참고한거긴 하지만 이게 가장 맞는답이었다. 여기서 포인트는 start 지점이 벡터 크기보다 낮는다를 while 조건에 포함시킨것과 product >= k 라는 핵심조건을 같은 while룹 안에 넣는것으로 i (start) 지점을 올린것이다. 내 처음 접근법과는 다르게 count 를 하나씩 올리는것도 아닌 i 와 j 의 차이점을 넣는것도 좋은 포인트였던거같다.
배운점:
1. 슬라이딩 윈도우 문제안에서 범위를 찾는거는 두 index간의 차이를 구하는게 용이하다.
2. 고정관념을 버리자
