[백준] 2018 수들의 합 5 - Java

문제

링크

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int startIndex = 1;
        int endIndex = 1;
        int sum = 1;
        int count = 1;

        while (endIndex != N) {
            if (sum == N) {
                endIndex++;
                sum += endIndex;
                count++;
            } else if (sum > N) {
                sum -= startIndex;
                startIndex++;
            } else {
                endIndex++;
                sum += endIndex;
            }
        }
        System.out.println(count);
    }
}

---

리뷰

투 포인터 알고리즘을 이용한 문제풀이이다.
N값의 범위가 최대 천만으로 O(N)의 시간복잡도를 가지는 방법으로 문제를 해결해야한다.

연속된 숫자의 합이 나타나는 가짓수를 구하는 문제로 startIndex와 endIndex 값을 이용해 배열을 순차적으로 진행하며 연속되는 숫자의 합이 주어진 숫자와 같아지는 경우 count한다.

생각보다 고급스러운? 알고리즘 이름에 어딘가 되게 단순해 보이는 코드이다.

아직은 알고리즘을 막 공부하기 시작해서 그런지 처음 백준, 프로그래머스 문제를 풀었었던 기분이 다시 느껴진다.

다양한 알고리즘을 배워나가는데에 설레기도 하는데 이 많은 애들을 다 이해하고 평소에 문제를 보면 이건 어떠한 알고리즘 문제로 풀면 되겠다 하는 느낌이 올 수 있나 싶은 불안감도 드는 것 같다 😬