코딩 테스트 [자료구조] - 투 포인터 / 연속된 자연수의 합 구하기

투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

---

어떠한 자연수 N은 몇 개의 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ⪯ N ⪯ 10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이떄 사용하는 자연수는 N이어야 한다. 예를 들어 15를 나타내는 방법은 15, 7 + 8, 4 + 5 + 6, 1 + 2 + 3 + 4 + 5이다. 반면 10을 나타내는 방법은 10, 1 + 2 + 3 +4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.

---

입력

1번째 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.

예제 입력
15	// N

예제 출력
4

---

1단계 - 문제 분석하기

N의 최댓값이 10,000,000으로 매우 크게 잡혀있으므로, O(nlogn)의 시간 복잡도를 사용하면 제안 시간을 초과한다. 그러므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.
이런 경우 자주 사용하는 방법이 투 포인터이다. 시작 인덱스와 종료 인덱스를 지정하여 연속된 숫자를 표현한다.

2단계 - 손으로 풀어 보기

1 입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 초기화한다.
결과 변수 count를 1로 초기화하는 이유는 N이 15일 때 숫자 15만 뽑는 경우를 미리 넣고 초기화했기 때문이다.

2 투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다.

투 포인터 이동 원칙

• sum > N : start_index++; sum -= start_index;
• sum < N : end_index++; sum += end_index;
• sum = N : end_index++; sum += end_index; count++;

3 2단계를 end_index가 N이 될때까지 반복한다.

3단계 - sudo코드 작성하기

N 변수 저장
사용 변수 초기화 (count = 1, start_index = 1, end_index = 1, sum = 1)

while(end_index != N){
	if(sum == N)
    	count 증가; end_index 증가; sum+= end_index;
    else if(sum < N)
    	end_index 증가; sum += end_index;
    else if(sum > N)
    	sum -= start_index; start_index 증가;
}

count 출력

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q6 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int sum = 1;

        while (end_index != N){
            if(sum == N){
                count += 1;
                end_index +=1;
                sum += end_index;
            } else if (sum < N) {
                end_index += 1;
                sum += end_index;
            } else if (sum > N) {
                sum -= start_index;
                start_index += 1;
            }
        }

        System.out.println(count);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편