투 포인터 (파이썬)

투 포인터 ?

투 포인터는 알고리즘을 풀 때 자주 쓰이는 방식이고 무엇보다 실행 속도가 빠르다고 한다.

나는 기존 배열 알고리즘에 대해 비효율적인 부르트 포스 방식을 사용했다.

부르트 포스는 비효율적일 뿐 만 아니라 실행속도도 낮다.

이 방법으로 문제를 풀면 time out이 나는 경우가 많다.

그리하여 사용해야할 방법은 투 포인터이다.

투 포인터에 대한 지금까지의 개념은 어떤 기준에 대해 left, right로 접근을 하는것이다.

빗물 트래핑의 경우, 제일 높은 블럭을 기준으로 양 옆으로 left, right를 움직이며 계산했다.

또, 세 수의 합의 경우에는 i를 기준으로 i의 바로 오른쪽 left, 리스트의 끝 right를 움직이며 작동한다.

투 포인터에 대해 조금은 알 것 같지만 아직 능숙하게 활용하지는 못한다.

최대한 문제를 풀때 투 포인터를 활용하기로 한다.

느낀 점 1

세 수의 합에서 투 포인터를 활용해 left, right를 사용하여 문제를 풀어 봤다.time out은 나지 않았지만, 매우 낮은 실행 속도를 보여줬다.왜냐? 안해도 될 작업을 하게 만들었다.

투 포인터의 핵심은 하지 않아도 될 작업을 하지 않게 시킨다라는 것 이라는 것 같다.

이 문제를 풀 때 나는 아래와 같이 중복된 수를 sorted()를 이용해 굳이 추가 시켰다.

if summary == 0 and sorted(list((lst[i], lst[l], lst[r]))) not in result:
                result.append(sorted(list((lst[i], lst[l], lst[r]))))

 

 

핵심은

if i > 0 and nums[i] == nums[i - 1]:
                continue
..............

while l < r and nums[l] == nums[l+1]:
    l += 1
while l < r and nums[r] == nums[r-1]:
    r -= 1

이 작업을 통해 중복되어 할 필요가 없는 작업은 그냥 pass시켜 주는 것..