[0818] 곱하기 or 더하기

문제

다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.

단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

주의점

• 숫자가 0 또는 1일 경우, 곱하는 것보다 더하는 것의 값이 더 크다.
• 함수 안에 있는 result의 값 또한 0 또는 1일 경우 곱하는 것보다 더하는 것의 값이 더 크다.

코드

def find_max_plus_or_multiply(array):
    result = 0
    
    for number in array:
      if number <= 1 or result <= 1:
        result += number
      else:
        result *= number
        
    return result


input = [0, 3, 5, 6, 1, 2, 4]
result = find_max_plus_or_multiply(input)
print(result)

시간 복잡도

result = 0							
    
for number in array:				
    if number <= 1 or result <= 1: 
      result += number
    else:
      result *= number

• 1차 반복문이 나왔고, array의 길이만큼 반복하므로 𝑶(𝑵)만큼의 시간 복잡도가 걸린다.
• 나머지 대입이나 비교에 의한 값들은 상수이므로 신경쓰지 않아도 된다.