[프로그래머스][Java][자바] 숫자의 표현

원본 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

 

 

처음 문제를 풀었을때 n * n 으로 풀었다. 레벨도 낮아서 1억개 그냥 계산 하겠지란 마인드 였다. 

하지만 효율성을 실패하고 다시 풀었다. 

 

그런데 알고리즘 보단 수학적 지식(알고리즘도 수학이지만)이 더 필요한 문제이다.

난이도가 낮음에도 불구하고 졸업한지 오래돼서 기억하느라 오래걸렸다. 

---

 

O(n) 으로 푸는 방법. 

//의사 코드

카운트 0으로 초기화
for(연속된 숫자의 시작 숫자는 1에서부터 n까지이다) {
    1. 연속된 숫자의 마지막으로 추정되는 값을 찾는다. 
    2. 마지막값으로 추정 되는 값이 마지막 값인지 확인한다.
    맞다면 카운트 하나 추가
    아니면 다음 숫자의 시작으로 반복
}

 

//코드

public int solution(int sum) {
    int count = 0;
    for (int start = 1; start <= sum; start++) {
    
        // 1. 마지막으로 추정되는 값 구하기
        int number = (2 * sum) + start * (start - 1);
        int last = (int) Math.sqrt(number);
        
        // 2. 합이 되는지 확인
        if ((last) * (last + 1) / 2 - (start - 1) * (start) / 2 == sum) {
            count++;
        }
    }
    return count;
}

 

 

---

 

• 연속된 숫자의 마지막 값으로 추정되는 값을 찾는다. 

 

last

Σ k

k = start

연속 되는 숫자의 합 기호는 이렇게 되고

(last == 연속된 숫자의 마지막, start == 연속된 숫자의 처음)

 

이것을 공식으로 풀어내면

(last) * (last + 1) / 2 - (start - 1) * (start) / 2 == 연속된 숫자의 합

(처음부터 마지막까지의 합) - (처음부터 연속된 숫자 시작점 직전까지의 합)

 

자바의 나누기는 몫이 나오기 때문에 양변에 2를 곱하고  start가 있는 항을 우변으로 옮기면

(last) * (last + 1)  == 연속된 숫자의 합 * 2 +  (start - 1) * (start)

 

n-1, n, n+1 의 제곱의 부등호 관계를 살펴보면  당연히 이렇게 되는데

(n-1) * (n-1) < n * n  < (n +1) *( n + 1)

 

여기서 위에서 구한 좌변의 항을 적용하면 이렇게 된다.

(n-1) * (n-1)   <   n * n    <   n * (n+1)   <   (n +1) *( n + 1)

 

여기서 n * (n+1)의 제곱근을 구하고 나머지를 버린다면

이 값은 정수이며 n-1 보다 크고 n + 1보다 작기 때문에 n이 된다.

n-1 < n = n < n+1

 

즉 (int) Math.sqrt( (last) * (last + 1) )해서 나오는 이 값은

연속된 수열의 마지막값으로 추정되는 정수 값이다. 

 

• 마지막으로 합이 되는 지 확인하기.

마지막 값으로 추정 되는 값이지 start부터 last까지 합이 n이 되지 않을 수 있기에 

마지막으로 합이 되는 지 확인 해 주고 맞다면 count를 올려주고 다음 반복으로 넘어간다.

 

 

---

• 연속된 숫자의 합이 100일떄