곱하기 혹은 더하기

 

문제

0에서 9로 이루어진 문자열이 있을 때, 순서대로 곱하거나 더하여 만들 수 있는 가장 큰 수를 구하라

 

유형파악

가장 큰 이라는 말이 나왔고 딱히 자료구조를 사용해야할 상황이거나 게임을 만드는 것과 같은 상황이거나 정렬 상황이거나 시간 복잡도를 크게 고려해야하는 상황이 아니라면 그냥 그리디 알고리즘이지 않나 싶다.

 

아이디어, 정당성 

우선, 가장 먼저 드는 생각은 곱하기를 많이 해야 큰 수를 만들 수 있다.

하지만 항상 그런 것은 아니고 0에 곱하기를 하면 안된다.

또한 1은 더하는게 더 큰 수를 만들 수 있다.

 

예를 0123456이 있을때

0+1 = 1

1+2 = 3

3*3 = 9

이런식으로 곱하기만 하면 안된다.

 

구현

피연산자 중 0이나 1이 있는지 체크해가며 연산을 진행하되 0, 1 이 아니면 곱하기를 한다.

 

코드

num = input("입력 : ")
result = 0
for i in num:
    if result <= 1 or int(i) <= 1:
        result += int(i)
    else:
        result *= int(i)
print(result)

 

 

시간 복잡도

숫자의 개수는 최대 100만이다. 근데 여기서 시간복잡도는 O(N)이므로 충분하다.

 

공간복잡도

고려할 필요가 없다.