10610번 30

문제 출처 : https://www.acmicpc.net/problem/10610

사고 과정

int형이 10^5개의 자리 수를 감당하지 못할 것 같아 list나 str로 해결하고자 생각했다.
str은 "불변"변수이기 때문에 str을 이용하여 값변경은 쉽지 않을 것이라 판단. list를 이용해야겠다. 이때 문제에서 숫자가 너무클것같아 list도 감당이 가능할까 싶어 list의 메모리에 대한 부분을 찾아봤다.

100,000,000 (일억)이 381MB 크기

문제는 기껏해봐야 100,000개의 List를 이용하니 문제 없겠다. list를 이용해 풀자!
30의 배수여야 하니까 주어진 N에 무조건 0이 존재해야겠지 그러면 3의 배수를 구하는 문제로 바뀐다!!
...

이 문제 그냥 문자열과 int 등 형 변환에 대한 간단한 문제... 괜히 어렵게 생각하지 말자ㅜㅜ
40분이나 걸렷네ㅜㅜㅜㅜ
그래도 시간, 공간 복잡도, 어떤 문제를 마주했을 때 어떤 자세로 풀어야 할지, 어떻게 하면 더 효율적으로 풀 수 있을지 생각해보게 되는 시간이 되는 문제.

1. 그냥 막무가내

import sys

N = list(sys.stdin.readline().rstrip("\n"))
num="".join(sorted(N,reverse=True))

if int(num)%30 == 0 :
    print(num)
else:
    print(-1)

형변환을 이용하여 생각없이 풀었다.

2. 생략가능한, 불필요한 부분 삭제

import sys

N = sorted(sys.stdin.readline().rstrip("\n"),reverse=True)
num = "".join(N)

if int(num)%30==0 : print(num)
else : print(-1)

3. 다른 사람것 참고

import sys

N = sorted(sys.stdin.readline().rstrip("\n"),reverse=True)
#-1이 출력되는 경우 조기에 join을 차단
if ("0" in N) and sum(map(int,N))%3==0 : print("".join(N))
else : print(-1)

파이썬스럽게? 가지치기를 통한 효율성 증가. 추가로 대수적인 부분( 모든 자릿수의 합으로 나누기가 결정 )을 추가하여 수정하였다.

list의 요소들의 값을 str-> int로 변경하기 위한 map의 이용. map을 적극적으로 활용해보자.