프로그래머스 - Lv.1: 자릿수 더하기

문제

풀이

def solution(n):
    return sum(map(int, str(n)))

시간복잡도

O(log n)

• n이 이미 10^8이므로, O(log n) 이하의 시간복잡도로 풀어야 함!

• str(n): 입력 정수 n을 문자열로 변환합니다. 이 변환은 n의 자릿수에 비례하므로 시간 복잡도는 O(log n)입니다. (자릿수가 늘어날수록 문자열로의 변환에 걸리는 시간이 늘어남)

• map(int, str(n)): 문자열로 변환한 n을 각 자릿수의 문자로 나누고, 각 문자를 정수로 변환합니다. 이 작업은 문자열의 길이에 비례하며, 시간 복잡도는 O(log n)입니다.

• sum(...): map 함수의 결과로 얻은 정수들을 모두 합하는 연산입니다. 이 작업은 입력 n의 자릿수에 비례하므로 시간 복잡도는 O(log n)입니다.

배운점

• str(n) 즉, 정수의 문자열 변환이 n의 자릿수에 비례하므로 시간복잡도가 O(log n)!
• map() 함수는 주어진 함수를 순회 가능한(iterable) 객체의 모든 요소에 적용하여 새로운 iterable 객체를 생성하는 파이썬의 내장 함수