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

문제


이 문제는 아무리 풀어도 효율성이 떨어졌다. 그 이유를 알기 전에 내가 접근했던 방법에 대해서 말하자면,

  • 숫자를 표현하는 방법이 숫자 1개로 표현하는 방법,
    숫자를 2개로 표현하는 방법 ⋯ 숫자 N개로 표현 하는 방법이 있다고 생각했다.

  • 숫자 N개를 1부터 계속해서 증가해 나가는데, 만약 숫자 (1~N) 까지의 합이 현재 확인해야하는 수보다 크면
    break를 거는 방법으로 했다.

  • 그리고 숫자 N에 맞춰서 원하는 target 을 표현하는 연속된 숫자의 첫번째 값 itarget 부터 1씩 내려가며 target == sum( i, i + n ) 이면 count를 1증가 시키고, n을 1증가시킨다.

  • 만약 target을 0까지 줄여도 나오지 않는다면, n을 1증가 시킨다.

이렇게 변수 i, n을 이용해서 target의 값을 찾았는데, 이렇게 할경우 현재 찾아야하는 값보다 더 큰 값을 찾을 때 break가 걸리기 때문에, 효율성에 문제가 생긴 것 같다.

접근법

  1. 찾아야하는 숫자(매개변수 n) 는,
    1개로 표현 하는 방법은 자기자신이다.
    2개로 표현 하는 방법은 n 이 홀수 일때, 찾을 수 있는데 (n / 2) 의 값을 초기로 갖는다.
  1. 따라서, 찾아야하는 숫자를 1개로 표현하는 방법을 제외하고 가장 작은 방법으로 표현하는 방법은 2개로 표현 하는 방법은 (n/2, n/2 + 1) 일때 이기 때문에,
    초기 값을 찾는 변수 i1부터 n // 2 까지 1씩 증가한다.
            for i in range(1, n // 2 + 1)
# i는 초기 값
  1. 초기 값이 i일때, 연속되는 숫자를 찾는다.
    연속되는 숫자의 합이 n보다 커질때 까지 반복문을 돈다. 연속되는 숫자의 합을 구하는 방법은
    sum_value = i + (i + 1) + (i + 2) ⋯
    과 같다.

이를, 코드로 표현하게 되면, 아래와 같이 표현 할 수 있다.

        sum_value = 0
        while sum_valne <= n:
            sum_value += i
            i += 1
            if sum_value == n:
                count += 1
                break

코드

  def solution(n):
      count = 0
      for i in range(1, n // 2 + 1):
          sum_value = 0
          while sum_value <= n:
              sum_value += i
              i += 1
              if sum_value == n:
                  count += 1
                  break
      return count + 1

좋은 웹페이지 즐겨찾기