(JAVA) 백준 2003번 : 수들의 합2 --- [투포인터]

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

안녕하세요.

 

투포인터의 기초 문제 입니다.

 

 

투포인터 알고리즘에 대해서는 별도의 포스팅에서 다뤄보겠습니다.

 

이 분이 작성하신 포스팅이 이해하는데 큰 도움이 되서 한 번 링크 적어봤습니다!

https://code0xff.tistory.com/128?category=723754

17. 투 포인터, 슬라이딩 윈도우 (1)

 

 

이 문제는 간단합니다.

즉, A 배열이 있을 때 A의 부분 배열 내 원소의 합이 M이 되는 갯수만 찾으면 되죠.

 

투포인터를 사용하기에 적합합니다.

*** 참고로, 시간 복잡도를 O(n^2) 에서 최대 O(n) 까지 줄일 수 있습니다.

 

 

투포인터 + 이 문제의 핵심만 적어본다면,

 

  1)  S, E 두 개의 포인터를 배열의 첫 번째에 두고 시작합니다. (포인터는 int 변수로, 인덱스를 가리킵니다.)

 

  2)  S는 Start Point(시작 점), E는 End Point(끝 점) 을 의미합니다.

 

  3)  S 포인터부터 E 포인터까지의 합 SUM과 M을 비교하면서 E 포인터가 배열의 끝에 닿을 때 까지 반복 진행됩니다.   

 

  4-1)  SUM >= M 인 경우, SUM을 줄여야 M에 가까워지므로, S 포인터를 1 증가 시킵니다. (오른쪽으로 한 칸 이동)

  4-2)  E 포인터가 끝 점에 도달했다면, S 포인터를 1 증가 시킵니다. (오른쪽으로 한 칸 이동)

  4-3)  SUM < M 인 경우, SUM을 늘리기위해 E 포인터를 1 증가 시킵니다.

  4-4)  SUM = M 인 경우, 하나 찾았으므로 count + 1 합니다.

 

*** 여기서 적지 않은 부분이 있는데, 포인터를 증가시켰을 때 S 포인터는 현재 위치의 원소를 SUM에서 제거 해야 하고, E 포인터는 현재 위치의 원소를 SUM에서 증가 시켜야 합니다.

*** 그 이유는, 현재 S ~ E 의 부분 배열의 전체 합을 구하고 있기 때문에 포인터가 옮겨지면 당연히 전체 합 또한 증감되기 때문입니다.

 

 

 

이상입니다.

 

감사합니다!

 

 

소스코드

---