[백준] 2018: 수들의 합 5 - JAVA(자바)

TMI: 며칠 전 실버 5로 승급했다🎉🎉

 

원래 책에 있는 모든 문제를 포스팅 하려 했지만... 생각보다 블로그 포스팅 시간이 꽤 걸려서(한시간 반 이상..ㅠ) 중요한 몇몇 문제들만 선별해서 포스팅하기로 했다. 이번 문제는 투 포인터를 이용한 문제라 정리하면 좋을 것 같아서 글을 올린다.

🧩 문제

Do it 알고리즘 코딩 테스트 자바편(구판) 006

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

 

 

🧠 접근 방법

입력값 N의 최댓값이 10,000,000(천만)이므로 제한 시간 2초 안에 풀기 위해서는 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

따라서 O(n)의 시간 복잡도를 가진 투 포인터(슬라이딩 윈도우) 방식으로 접근했다. 

그럼 투 포인터란 무엇일까?

 

투 포인터

1차원 배열에서 사용할 수 있는 알고리즘으로, 배열의 특정 요소를 가리키는 2개의 포인터를 조작해가면서 원하는 값을 찾아내는  알고리즘이다. 

O(n)의 시간 복잡도를 가진다.

 

start_index와 end_index를 투 포인터로 지정하여 연속된 수를 표현했다.

 

✨투 포인터 이동 원칙

• sum == N: count 증가, end_index 증가, sum 재할당
• sum > N: sum 재할당, start_index 증가
• sum < N: end_index 증가, sum 재할당

중요한 점은 두 포인터 모두 한 방향으로만 이동한다는 것이다.

 

💻 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P2018_연속된자연수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int start_index = 1, end_index = 1, sum = 1, count = 1;
        while (end_index != N) {
            if (sum == N){ // 현재 연속 합이 N과 같은 경우
                count++;
                end_index++;
                sum += end_index;
            } else if (sum > N) { // 현재 연속 합이 N보다 큰 경우
                sum -= start_index;
                start_index++;
            } else { // 현재 연속 합이 N보다 작은 경우
                end_index++;
                sum += end_index;
            }
        }
        System.out.println(count);
    }
}

초기 count 값을 1로 한 이유는 N 자기 자신 하나로 표현하는 경우를 포함하기 위함이다.

이렇게 하면 간단하게 연속된 자연수의 합을 구할 수 있다.

 

📊 시간 복잡도 및 결과

⏱️시간 복잡도

• start_index는 최대 N번 증가
• end_index도 최대 N번 증가

두 포인터가 각각 한 번씩만 앞으로 이동하므로 전체 시간 복잡도는 O(N) 이다.

 

✅ 제출 결과