그리디(탐욕법) 알고리즘 - 곱하기 혹은 더하기

문제 설명

각 자리 숫자(0~9)로만 이뤄진 문자열 s가 주어졌을때, 왼쪽부터 오른쪽까지 하나씩 모든 숫자를 확인하며 숫자사이에 'X' 혹은 '+' 연산자를 넣어 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 단 모든 연산은 왼쪽부터 순서대로 이루어진다.

 

문제 해결 아이디어

• 두 수 중에 하나라도 0 or 1이면 더하기를 수행, 예외 경우는 곱하기수행

풀이 : O(N)의 시간 복잡도

data = input()

result= int(data[0])

for i in range(1,len(data)):
    num=int(data[i])
    if num<=1 or result<=1:
        result+=num
    else : result*=num

print(result)