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

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

프로그래머스

 

주어진 숫자n를 연속하는 자연수의 합으로 표현할 수 있는 경우의 수를 구하는 문제이다.

 

Lv 2 문제로 넘어오면서 정확성 테스트 뿐만 아니라 효율성 테스트까지 통과해야 문제를 풀 수 있다.

 

어제 아침에 이 문제를 풀었는데

처음에는 0부터 n까지 각각 0부터 자기자신까지 더한 합을 리스트에 저장한 뒤

for문을 돌면서 n을 리스트 내의 요소들의 차로 표현할 수 있는지 검사한 뒤 경우의 수를 +1했다.

 

정확성 테스트는 통과했지만 효율성 테스트는 통과하지 못했다.

 

오늘 아침에 다시 효율성 테스트를 통과하기 위해 코드를 수정했다.

처음에는 로직은 그대로 두고 구현 방법을 고민했다.

1. ArrayList는 메모리 공간이 정해져있기 때문에 add할 때마다 시간이 오래 소요되어서 그런가? 

라는 생각이 들어서 미리 최대 크기로 지정한 배열에 값을 하나씩 대입한 뒤 Arraylist로 변환해서 리스트의 contains 메소드를 사용해 값을 찾았다. -> 시간 초과

2. 배열을 Arraylist로 변환하는 과정에서 시간이 오래 걸리나?

그래서 Arraylist를 사용하지 않고 for문을 다시 돌아서 찾는 값이 있는지 확인했다. -> 시간 초과

3. for 문 내에서 n부터 찾지 말고 n/2+1부터 0까지만 찾으면 되지 않을까?

시간은 좀 줄었지만 여전히 시간초과가 났고 무엇보다 정확성 테스트에서 틀린 경우가 생겼다.

n부터 찾지 않아서 미리 answer = 1로 초기화했는데 n=1인 경우에는 n/2+1 = 1이기 때문에 중복되었다.

 

로직을 그대로 두고 구현 방법을 바꾸는 방법으로는 효율성 테스트를 통과하지 못할 것 같다는 생각이 들었고 다른 로직을 고민했다.

 

손으로 문제를 풀다보니 (0부터 i까지의 합 - 0부터 j까지의 합 = n을 구한다고 할 때)

n과 첫 번째 for 문 내에서 i가 주어진다면 나머지 숫자 j 를 2차방정식의 근의 공식으로 구할 수 있겠다는 생각이 들었다.

그러면 2중 for문을 for문 하나로 줄일 수 있어서 효율성 테스트를 통과할 수 있겠다는 확신이 들었다. -> 통과 !

 

그리고 구현한 코드는 다음과 같다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=n;i>0;i--){
            double m = (double) (-1 + Math.sqrt(1 + 4 * (i * i + i - 2 * n))) /2;
            if(m%1==0.0 && m < i) answer++;
        }

        return answer;
    }
}