2024.05.18 - 숫자의 표현

[wlsgh7608]

문제 - 링크

문제 풀이

• 연속된 자연수들로 숫자 n을 만드는 경우의 수 구하기
• ex) 15
  • 1, 2, 3, 4, 5
  • 4, 5, 6
  • 7, 8
  • 15

문제 풀이 로직 1

• 투 포인터

구간의 합이 n미만일 경우 right을 한 칸 이동한다!

구간의 합이 n이상일 경우 left을 한 칸 이동한다!

        int cnt = 0;
        int l = 1;
        int r = 1;
        int sum = 1;
        while (l <= r && r <= n) {
            if (sum == n) {
                cnt++;
            }

            if (sum < n) {
                r++;
                sum += r;
            } else if (sum >= n) {
                sum -= l;
                l++;
            }
        }

코드

import java.util.*;

class Solution {
    public int solution(int n) {
        // 자연수 n 표현하기
        // k, k+1, ..., n-1, n을 만족하는 개수 구하기
        int cnt = 0;
        int l = 1;
        int r = 1;
        int sum = 1;
        while (l <= r && r <= n) {
            if (sum == n) {
                cnt++;
            }

            if (sum < n) {
                r++;
                sum += r;
            } else if (sum >= n) {
                sum -= l;
                l++;
            }
        }
        return cnt;
    }
}

시간, 공간 복잡도

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

실행 시간