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

문제 접근

문제 예시를 보고 자연수 n을 표시한 방법에 대해 고민했다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

1. 1부터 n까지 1씩 증가한 값을 더해 n 표현

2. 1부터 n/2까지 1씩 증가한 값을 더해 n 표현

3. n/2부터 n까지 1씩 증가한 값을 더해 n 표현

4. n 자체로 표현

이 접근을 토대로 하면 자연수 n을 표시하는 경우의 수는 최대 4가지다.

그리고 이 로직으로 문제를 푼다면 코드가 길어질 것 같은데

대체로 코드가 길어질게 예상되면 문제를 틀리는 경우가 많아 다른 방법을 더 고민해봤다.

 

첫 번째 예시를 보면 1부터 n까지의 항들이 모두 1씩 증가한다.

따라서 이 수열은 등차수열이다.

등차수열의 합으로 등차수열의 경우의 수를 구하는 수학 문제인가 싶어 자괴감이 들 때 쯤 한 동료가 단순하게 생각해보라고 조언했다.

 

생각해보니 변수를 선언해 1 부터 n까지 증가시켜가며, 이 변수부터 n까지의 수를 반복해 더하면 된다고 판단했다.

def solution(n):
    answer = 0

    for i in range(1, n + 1):
        sum = 0
        num = i
        while sum < n:
            sum += num
            if sum == n:
                answer += 1
            num += 1

    return answer

---

동료들과 이 문제를 풀며 알게된 사실

 

• 자바는 파이썬보다 빠르다

효율성 테스트의 실행 속도에 있어 4ms 정도 차이가 있었다.

 

• 이중 for문을 사용한 동료보다 for문과 while문을 사용한 코드가 조금 더 빠르다

테스트 케이스 하나에서 3ms 차이가 났다.

크게 차이가 나는 것은 아니지만, 내 코드에서는 while문의 조건식에서 sum이 n 보다 크거나 같으면 반복문을 즉시 종료한다.

def solution(n):
    answer = 0

    for i in range(1, n + 1):
        sum = 0
        num = i
        while sum < n: # sum >= n이 될 경우, 조건식만 실행 후 반복문은 종료된다.
            sum += num
            if sum == n:
                answer += 1
            num += 1

    return answer

 

반면 이중 for문을 사용한 동료는 안쪽 반복문에서 i부터 n까지 반복을 수행하기 때문에,

num이 n보다 클 때 break를 통해 반복문을 종료한다.

이 과정에서 num이 n보다 큰 경우에도 반복문의 코드블럭을 실행하기 때문에 속도 차이가 나는 것 같다.

  for i in range(1, n+1): 
  	 sum = 0
     for j in range(i, n+1): 
         sum += j
         if sum == n:
             answer += 1
             break
    	 elif sum > n: # 위 코드를 모두 실행한 뒤 elif 조건식을 만난 다음 반복문이 종료된다
         	break

 

사실 나도 이중 for문을 사용해 문제를 풀어봤지만 시간 초과가 났다.

def solution(n):
    answer = 0
    
    for i in range(1, n+1): 
    	sum = 0
        for j in range(i, n+1): 
            sum += j
            if sum == n:
                answer += 1
                break
        
    return answer

동료의 코드를 보면 알 수 있다시피, 나는 sum == n이 되는 경우만 판단하면 된다고 생각했다.

그래서 해당 조건에 걸리지 않는 수열의 루프를 돌 때 탈출할 수 있는 코드가 없다.

따라서 O(n^2)의 시간복잡도를 갖게 되어 최악의 경우, 1억 번(최대 입력값 10,000 ^ 2)의 연산을 수행하게 된다.