알고리즘 더 풀어보기 (1)

[곱하기 or 더하기]

문제) 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

 

무조건 곱하기만 한다고 커지지 않음!

- 0과 곱하게 되면 값이 0이 나옴 : 더하는게 나음

- 1과 곱하게 되면 값이 커지지 않고 그대로임 : 더하는게 나음

∴ 계산하려는 값이 1 이하일 경우 더하기

 

앞숫자 + 뒤숫자        <- 이렇게 더할 때 앞숫자 또는 뒤숫자가 1이하여야 하는 것을 놓치지 말기

 

#1보다 크다면 곱하는 게 낫다

input = [0, 3, 5, 6, 1, 2, 4]


def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for number in array:
        if number <= 1 or multiply_sum <= 1:   #앞숫자 또는 뒤숫자가 1이하
            multiply_sum += number
        else:
            multiply_sum *= number
    return multiply_sum


result = find_max_plus_or_multiply(input)
print(result)

 

[시간복잡도]

O(N)

함수 구문 하나하나 보지 않더라도, 1차 반복문이 나왔고, array만큼 반복한다면

O(N)이겠구나 하면 됨! 계수는 신경 안써도 되는거니깐