[프로그래머스 / JavaScript] 숫자의 표현

-- 문제

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

프로그래머스

---

-- 최초 풀이

function solution(n) {
    let cnt = 0;
    let i = 1;
    
    // 예외 처리
    if (n === 1) return 1;
    
    while (1) {
        let mid = Math.ceil(n / i); // 중앙값
        
        // 연속된 수 중 가장 작은 값이 1보다 작으면 루프 종료 및 cnt 리턴
        if (mid - Math.floor(i / 2) < 1) return cnt;
        
        if (n % mid === 0) cnt++;
        else if (n % (mid * 2 - 1) === 0) cnt++;
        
        i++;
    }
}

 

-- 접근 과정

매개변수 n이 1일 때는 1을 리턴하도록 예외 처리를 먼저 해 준 다음,

중앙값을 먼저 구하고, 만들어 질 연속된 수 중 가장 작은 값이 1보다 작게 되면 while loop를 종료하도록 했다.

그 다음, 중앙값으로 n이 나누어 떨어지면 cnt 증가

혹은 중앙값(소수점 올림) * 2 - 1으로 n이 나누어 떨어지면 cnt 증가

로 코드를 짰다.

 

하지만, 제출 결과 62.5점이었다.

 

최초 풀이대로라면,

#TC : n = 100

i 가

〉	1 2 4 5 8 10 11

일 때 cnt 가 증가하게 되는 데

알다시피 i 가 2인 경우에는 연속된 수의 합으로 100을 만들 수 없다.

(중앙값이 50이면서, 만들 수 있는 49 + 50 과 50 + 51 둘 다 100 이 되지 않음)

 

실제로는

100 = 100

100 = 18 + 19 + 20 + 21 + 22

100 = 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16

이렇게 3가지 경우만 나온다.

 

그래서 위의 코드를 최대한 바꾸지 않으면서 문제를 해결하려 했으나, 로직이 떠오르지 않아

결국 중앙값을 기준으로 한 연속된 수 배열을 만들어 합이 100인 지 확인하는 방식으로 갔다.

 

-- 최종 제출

function solution(n) {
    let cnt = 0;
    let i = 1;
    
    while (1) {
        let mid = Math.ceil(n / i);
        
        // 중앙값 기반 배열 길이가 i인 연속된 수 배열 생성
        let arr = Array(i).fill(mid).map((v, idx) => v + idx - ~~(i / 2));
        if (arr[0] < 1) return cnt; // 배열 중 가장 작은 값이 1 미만이면 루프 종료
        
        if (arr.reduce((acc, cur) => acc + cur, 0) === n) cnt++;
        
        i++;
    }
}

 

제출 결과 모든 케이스를 통과했지만 굳이 배열을 만들지 않고 수학 계산만으로 풀 수 있는 방법이 있을 것 같았다.

그래서 다른 분의 풀이를 참고했다.

 

-- 다른 분의 풀이 참고

function solution(n) {
    var answer = 0;
    for (var i = 1; i <= n; i++) {
        if ((n % i == 0) && (i % 2 == 1)) {
            answer++;
        }
    }
    return answer;
}

 

i 가 1부터 n 까지 for loop를 돌려 n을 i 로 나눈 나머지가 0이고, i 가 홀수인 경우 answer를 증가하도록 했다.

1시간 동안 고민했지만 이렇게 풀이할 생각을 미처 하지 못했다.

하지만 이 경우에는 방법을 생각 못 했다는 것에 초점을 맞추지 말고, 패턴으로 기억해 두었다가 비슷한 문제를 다시 만났을 때 적용해 볼 만 한 것 같다.

 

(+ 내 최종 풀이 vs 다른 분 풀이 효율성 비교)

다른 분 풀이

내 최종 풀이