[ BOJ 오답노트 ] 2231 파이썬 : 분해합

2022 02 07

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 아주 다채롭게 오류가 났다^_^

 

(1) 런타임에러 (IndexError)

나는 처음에 이 문제를 1부터 n까지의 모든 수에 대해서 생성자의 분해합을 구해서 리스트에 저장하는 오류를 저질렀다. 근데 내가 리스트의 크기를 (입력받을 수 있는 가장 큰 값 + 1)을 했는데, 당연히 분해합은 그 값보다 크기 때문에 indexError가 났던 것이다.

lst = [[] for _ in range(1000053)]
n = int(input())
lstIdx = 0

for i in range(1, n+1):
    num = i
    sum = num
    while num // 10 != 0:
        sum += num % 10
        num //= 10
    sum += num

    lst[sum].append(i)
    lstIdx += 1

if lst[n] != []:
    print(min(lst[n]))
else:
    print(0)

 

 

(2) 시간초과

굳이 1부터 n까지 구할 필요가 없다는 것을 깨닫고, while문으로 하나씩 연산을 하면서 구한 분해합과 입력한 값이 같아졌을 때를 출력하려고 했다. 결과는 아주 잘 나오지만, 입력할 수 있는 최댓값인 1000000을 넣으니까 시간 제한 2초를 넘어서게 되었다.

# lst = [[] for _ in range(1000001)]
n = int(input())

i = 1
while True:
    num = i
    sum = num
    while num // 10 != 0:
        sum += num % 10
        num //= 10
    sum += num

    # 분해합이랑 n이랑 같아지면 그 때의 i 값이 생성자
    if sum == n:
        print(i)
        break
    else:
        i += 1

        # i 값이 증가하다가 n까지 가게 되면 생성자가 없다고 판단
        if i == n:
            print(0)

 

 

 

3. 해결

- while문 안에 또 while문으로 각 자리 숫자를 더하는 연산을 해서 시간 오류 판정을 받았던 것이다. 그래서 리스트의 아주 유용한 함수인 sum 함수와 map 함수를 사용하기로 했다.

- 그리고 val 값을 기본값으로 False로 해준 후에 만약에 생성자 값이 존재한다면 True로 바꿔주어서 0을 출력하지 않도록 한다.

 

 

 

4. 배운 점

- 시간 초과에는 반복을 줄이는 것이 답이다.

- 숫자의 각 자리 수를 더할 때에는 굳이 while문으로 하나씩 구해서 더하지 말고, sum 함수와 map 함수를 쓰자!