[B]BOJ2003 수들의 합 2 - 메모리 초과 코드, 정답 코드

 

코드는 깃헙 레포 참고

1. Brute force

포인터만 2개 활용하기는 했는데

로직이 그냥 이중 for문이라 투 포인터 풀이는 아님.

로직

p1 포인터는 수열을 순회하며 한 칸 씩 이동하고

    이 순회 루프 내에서 p2 포인터는 p1+1 index부터 시작하여
      - M이 total값보다 커지거나

      - p2 index가 N에 도달할 때까지

      array[p2] 값을 total에 합산함.

    위 조건에 의해 p2 index의 nested loop가 탈출하면

    - tot값을 검사하여 M과 일치하면 카운터 cnt 증가

    - 초과해버리면 p1을 한 칸 씩 이동시켜 다음 루프 수행. 

<최하단 제출> : Python3으로 제출하니 시간 초과됨.

<그 위 제출> : Pypy3로 제출하니까 시간 내에 수행됨.

2. Two pointer 코드

right pointer, p2를 left로 초기화 시키지 않고

while문이 알아서 증가시키게 한다.

그렇다면 left pointer p1가 맨 바깥 for문에 의해 한 칸 이동하고 나서

partial_sum -= arr[p1]을 해 주는데,

 

left pointer, p1가 한 칸 이동함에 따라

l의 이전 원소를 빼주어 부분합 개념을 유지한다. 

슬라이딩 윈도처럼 부분합의 range가 이동하는데

크기가 고정된 것이 아니라

partial_sum < M, p2 < N-1 의 조건에 따라

변화한다고 보면 된다.

<최상단 제출> : Python3으로 제출했으며 시간, 메모리 면에서 우수

* Bonus

  left를 고정시킨 뒤에는 r을 찾을 때,
  M과 일치하는 r이 존재하는지 없는 지가 결정된다.

  

  r을 찾는 방법으로

  - Right pointer index를 하나씩 증가시키는 방법도 있고

  - 뒤에서부터 이분 탐색을 통해 r을 찾는 방법도 있는데

전자의 경우 O(n), 후자의 경우 O(nlogn)의 시간 복잡도를 가진다.