투 포인터 - 수들의 합

🔎 문제

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

---

🔍 문제 분석

N의 최대 값은 10,000,000으로 크게 잡혀있고, 시간 제한은 2초이다. O9nlongn)의 시간 복잡도 알고리즘을 사용하면 제한시간을 초과하기 때문에 O(n)의 시간 복잡도 알고리즘을 사용해야한다. 이런 경우 자주 사용되는 것이 투 포인터

---

⏱ 시간복잡도 O(n)

---

👀 코드

import java.util.Scanner;

public class BackJoon_2018 {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int start_index = 1;
        int end_index = 1;
        int count = 1;
        int sum = 1;
        
        while(end_index != N) {
            if(sum == N) {
                end_index++;
                sum += end_index;
                count++;
            }
            else if(sum > N) {
                sum -= start_index;
                start_index++;
            }
            else if(sum < N) {
                end_index++;
                sum += end_index;
            } 
        }

        System.out.println(count);
    }
}