[백준 2018] 문제로 이해하는 투 포인터 JAVA

투 포인터 

투 포인터(Two Pointers)는 두 개의 포인터를 이용해 문제를 효율적으로 해결하는 알고리즘 기법입니다.
이 기법은 주로 정렬된 배열이나 연속적인 구간에서 조건을 만족하는 값을 찾을 때 사용됩니다.

 

투 포인터 사용 이유 🤔

투 포인터는 O(N) 또는 O(N log N)의 시간복잡도로 문제를 해결할 수 있으며, 특히 정렬된 배열에서 최적화된 탐색이 가능하다는 점이 큰 장점 입니다.

 

투 포인터의 기본 동작 방식 🎯

포인터 초기화

보통 시작점 left 와, 끝점 right 를 배열의 양 끝에 둡니다.

 

조건 확인

두 포인터가 가리키는 값이 조건을 만족하는지 확인합니다.

 

포인터 이동

조건에 따라 왼쪽 포인터 또는 오른쪽 포인터를 이동시킵니다.

 

포인터가 서로 교차할 때까지 반복

두 포인터가 교차하면 탐색을 종료합니다.

---

문제로 보는 투 포인터

연속된 자연수의 합 구하기 (백준 2018)

 

문제

 

출력

 

풀이

 

투 포인터 이동 원칙

sum > N 일 때,
sum = sum - start_index; / start_index++;

sum < N 일 때,
end_index++; / sum = sum + end_index;

sum == N 일 때,
end_index++; / sum = sum + end_index; / count++;

 

 

count를 1로 초기화 하는 이유는 N = 15 일 때, 숫자를 15만 뽑는 경우의 수를 미리 넣고 초기화 했기 때문입니다.

 

sum < N 일 때,
end_index++; / sum = sum + end_index;

 

10 < 15 일 때,
end_index ++;  /  sum = 10 + 5 를 실행  

 

 

sum == N 일 때,
end_index++; / sum = sum + end_index; / count++;

 

15 == 15 일 때,

end_index++;  /  sum = 15 + 6  /  count ++;
( N과 sum을 비교하여 값이 같으므로 count++ 을 해줍니다. )

 

 

sum > N 일 때,
sum = sum - start_index; / start_index++;

 

21 > 15 일 때,

sum = 21 - 1  /  start_index ++;

 

코드

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine()); // 15
    int N = Integer.parseInt(st.nextToken());

	// 시작 값 초기화
    int start_index = 1;
    int end_index = 1;
    int sum = 1;
    int count = 1;

    while (end_index != N) { // end_index가 N에 도착하면 종료
      if (sum == N) {
        count++;
        end_index++;
        sum += end_index;
      } else if (sum < N) {
        end_index++;
        sum += end_index;
      } else { // sum > N
        sum -= start_index;
        start_index++;
      }
    }
    System.out.print(count);
  }
}

 

투 포인터, 문제를 통해 배우다 ✍️

투 포인터는 개념적으로 설명하기보다 문제를 풀어보며 배우는 것이 가장 효과적입니다.
그래서 간단한 문제를 풀어보며 투 포인터의 작동 방식을 학습해 보았습니다! 😊