프로그래머스 - Lv.1: 자연수 뒤집어 배열로 만들기

문제

풀이

def solution(n):
    answer = []
    for i in str(n)[::-1]:
        answer.append(int(i))
    return answer

시간복잡도

O(log n)

• 제한조건: n이 최대 10^10일 수 있다. 10^8을 이미 초과하니까 시간복잡도는 O(n) 미만이어야 한다.

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

• [::-1]: 문자열을 뒤집는 연산입니다. 이는 문자열의 길이에 비례하므로 O(log n) 시간이 걸립니다.

• 전체 반복문은 이 문자열의 길이에 비례하는 횟수만큼 실행되므로 시간 복잡도는 O(log n)입니다.

• answer.append(int(i)): 현재 순회 중인 문자 i를 정수로 변환하고, 변환된 값을 리스트 answer에 추가합니다. 이 부분은 반복문 내에서 실행되므로 전체 반복문의 실행 횟수에 비례합니다. 따라서 시간 복잡도는 O(log n)입니다.

배운점

문자열 뒤집는 연산 -> [::-1]
이 과정은 문자열의 길이에 비례하므로 시간복잡도는 O(log n)