[프로그래머스 Lv.2] 숫자의 표현

풀이 날짜 : 2025.04.21
문제 유형 : 연습문제
문제 제목 : 숫자의 표현
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12924

 

Intuition

• 자연수 n을 연속된 자연수의 합으로 나타낼 수 있는 방법의 수를 구하는 문제이다.
  예를 들어 n이 15라면, 1+2+3+4+5, 4+5+6, 7+8, 15 의 네 가지 방법이 있다.
• n/2보다 큰 자연수부터 시작하는 자연수의 합은 없다. 따라서 자연수의 합은 n/2 보다 작은 수부터 시작하는 점을 고려한다.
• n 자체로만 표현되는 엣지케이스 한 가지가 있다.

 

Approach

• 연속된 자연수의 합으로 나타낼 수 있는 방법의 수를 저장하는 변수 answer를 선언한다.
  • 자기 자신은 무조건 포함되므로 1로 선언한다.
• for 루프
  • 1부터 시작하여 n/2 보다 작은 자연수까지 반복한다.
  • 자연수의 합을 저장하는 변수 sum, 자연수 합의 시작하는 변수 start를 선언한다.
• while 루프
  • sum에 start를 누적하고 반복할 때마다 start를 1씩 증가시킨다.
  • sum이 n보다 작을 때까지만 반복한다.
  • sum이 n과 같아졌다면 answer를 1 증가시킨다.
• answer를 반환한다.

 

Complexity

• Time complexity : O(n²)
  • for 루프에서 n/2번 반복하므로 O(n), while 문에서도 최악의 경우 n회에 가깝게(실제로는 n보다 작지만) 반복한다. 따라서 대략적으로 O(n²) 으로 보인다.

• Space complexity : O(1)
  • 별도의 배열이나 자료구조가 사용되지 않으므로 O(1)이다.

 

Code

function solution(n) {
    let answer = 1;
    
    for (let i = 1; i < n/2; i++) {
        let sum = 0;
        let start = i;
        
        while (sum < n) {
            sum += start
            start += 1;
        }
        
        if (sum === n) {
            answer += 1;
        }
    }
    
    return answer;
}

 

다른 방식의 코드 : 투 포인터 or 슬라이딩 윈도우 방식

• start, end는 연속된 자연수 구간의 시작과 끝을 의미하고, 1부터 시작한다. sum은 그 구간의 합이다.
  합이 n보다 작으면 end를 늘려서 sum에 더한다.
  합이 n보다 크면 start를 줄여서 sum에 더한다.
  합이 n과 일치하면 이를 카운트하고 다음 구간(start + 1)로 넘어간다.
  자기 자신이 되는 경우의 수를 포함하여 정답을 반환한다.
  
  
• start, end는 두 개의 포인터가 되어 한 방향으로 움직인다. 
  각각 최대 n회 이동하므로 시간복잡도는 O(n)이 되어 더 효율적인 코드가 된다.

function solution(n) {
    let answer = 0;
    let start = 1, end = 1, sum = 1;

    while (start <= n / 2) {
        if (sum === n) {
            answer++;
            sum -= start;
            start++;
        } else if (sum < n) {
            end++;
            sum += end;
        } else {
            sum -= start;
            start++;
        }
    }

    return answer + 1;
}