[백준 2231번 파이썬] '분해합' 모든 풀이 비교 분석

문제

자연수 N의 분해합은 N과 N의 각 자리수를 더한 값이다. 예를 들어, 245의 분해합은 다음과 같다.

245 + 2 + 4 + 5 = 256

이때, 245는 256의 생성자가 된다. 생성자는 여러 개일 수 있으며, 생성자가 없는 경우도 있다.
우리의 목표는 주어진 자연수 N에 대해 가장 작은 생성자를 찾는 것이다.

---

배경지식

이 문제는 브루트 포스 알고리즘 단계에 들어가 있다. 브루트 포스 알고리즘에 대해 간단히 알아보자면, 브루트(Brute)는 무식한 이라는 뜻이다. 한마디로 무식하게 다 해보는 알고리즘을 브루트 포스 알고리즘이라고 한다.

노가다의 예시를 잘 보여주는 사진이다.

논리 및 아이디어

1. 값을 입력받는다.(입력받은 값: n)

2. 1부터 n-1까지 해당 숫자와 자릿수를 모두 더해 생성자인지 확인한다.

3. 생성자가 맞다면 반복문을 깨고 나온다.

---

나의 풀이

코드

num = int(input())
testnum = 0
SumOfComposition = False

while testnum < num:
    totsum = testnum
    for i in str(testnum):
        totsum += int(i)
    if totsum == num:
        SumOfComposition = True
        break
    testnum += 1

if SumOfComposition:
    print(testnum)
else:
    print(0)

코드 설명

1. num에 입력값을 저장한다.
2. testnum을 0으로 초기화하고, SumOfComposition을 False로 설정한다.
3. while 루프를 통해 testnum이 num보다 작을 동안 반복한다.
4. totsum에 testnum 값을 저장하고, testnum의 각 자리수를 더한다.
5. totsum이 num과 같으면 SumOfComposition을 True로 설정하고 루프를 종료한다.
6. 루프가 종료되면 SumOfComposition의 값에 따라 testnum 또는 0을 출력한다.

실행시간은 188ms 나왔다.

 

---

다른 코드

코드

n = int(input())
result = 0
for i in range(1, n):
    a = list(map(int, str(i)))
    s = i + sum(a)
    if s == n:
        result = i
        break
print(result)

코드 설명

1. n에 입력값을 저장한다.
2. result를 0으로 초기화한다.
3. for 루프를 통해 1부터 n-1까지 반복한다.
4. i를 문자열로 변환한 후, 각 자리수를 정수로 변환하여 리스트 a에 저장한다.
5. i와 a의 합을 계산하여 s에 저장한다.
6. s가 n과 같으면 result에 i를 저장하고 루프를 종료한다.
7. 루프가 종료되면 result를 출력한다.

실행시간이 316ms 나왔다.

---

코드 비교 및 분석

공통점

• 두 코드 모두 브루트 포스 방식을 사용하여 1부터 N까지의 모든 수를 탐색한다.
• 각 자리수를 더하는 방법으로 분해합을 계산한다.

차이점

두 코드는 거의 비슷하다. 그러나 실행시간이 더 오래 걸렸다. 다른 코드1의 코드를 여러 번 다시 실행해본 결과 평균적으로 300ms 걸렸다. 

자릿수를 더하는 과정이 그 원인이라고 생각한다. for문으로 직접 더하는 방식보다 map과 list를 이용하는 방식은 코드는 간단하지만 오버헤드가 더 클 수 있다. 

 

---

개선할 점

무엇보다 탐색을 1부터 n-1까지 모두 할 필요가 없었다.

1. 탐색하는 수가 일정 이상 커지면 모든 자릿수를 더하면 생성자가 될 수 없다. 

2. 각 자릿수는 최대 9이다. 3자리 수는 각 자릿수가 9일 때, 자릿수의 합이 27이므로, (N-27) 부터 N-1까지만 탐색하면 된        다. 2자리 수는 18을 뺀 수부터 탐색하면 될 것이다. 따라서 최적화된 범위는  N - (N의 자리수 * 9) 부터 N-1까지이다. 

• 탐색 범위 최적화: 생성자는 최대 N - (N의 자리수 * 9)까지 가능하므로, 탐색 범위를 줄이면 실행 속도가 빨라진다.
• 자리수 합 계산 간소화: map과 sum 함수를 사용하여 더 간결한 코드를 작성할 수 있다.
• 코드 가독성 향상: 변수명을 명확하게 하고, 불필요한 변수를 제거하여 더 깔끔한 코드를 만들 수 있다.

최적의 코드

n = int(input())
for i in range(max(1, n - len(str(n)) * 9), n):
    if i + sum(map(int, str(i))) == n:
        print(i)
        break
else:
    print(0)

개선된 코드 설명

1. n에 입력값을 저장한다.
2. for 루프를 통해 가능한 생성자 범위를 탐색한다.
3. i와 i의 각 자리수의 합이 n과 같으면 i를 출력하고 루프를 종료한다.
4. 루프가 종료될 때까지 생성자를 찾지 못하면 0을 출력한다.

실행시간이 92ms로 확연히 줄었다.

---

출처

다른 코드 1의 출처
문제