[알고리즘] 곱하기 or 더하기

오늘 들었던 내일배움캠프 알고리즘 강의의 문제! 이름은.. 곱하기 or 더하기 (?) 인것같다

(강사님께서 말씀하시길 페이스북 기출문제 였다고 한다. 아마도 엄청 과거이지 않을까 싶다)

 

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

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

 

 

요약하자면, 왼쪽부터 숫자들끼리 하나씩 더하거나 곱해서, 만들 수 있는 가장 큰 수를 찾아라!

 

 

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

def findMaxPlusOrMultiply(array):
#구현
	return 0



result = findMaxPlusOrMultiply(input)
print(result)

이 함수 내부를 구현하면 된다!

결과값이 728이 나오면 성공!

 

 

 

 

 

 

pseudo code 의사코드

 

1. 필요한 주요 변수

  1) 연산 후의 결과를 담을 result

  2) 연산할 값 n

 

2. +(더하기), *(곱하기) 중 어떤 연산자를 써야 최종값이 더 커질까?

  1) 더해야 하는 경우 = 연산값 n이 0과 1 일 경우, (n <= 1)

  2) 곱해야 하는 경우 = 연산값 n이 0과 1이 아닐 경우. (n > 1)

 

3. 어떤 상황에 예외처리가 필요할까?

  1) n>1이지만, result <= 1 이어서 곱하지 않고 더해줘야 하는 경우

 

 

 

전체 코드

 

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


def findMaxPlusOrMultiply(array):

    result = 0

    for num in array:

        if result <= 1 or num <= 1: 	# 의사코드 2-1과 3-1에 대한 처리!
            result += num
        else:				# 의사코드 2-2에 대한 처리!!
            result *= num

    return result


result = findMaxPlusOrMultiply(input)
print(result)

 

반복문을 통해 간단하게 구현이 가능!

 

문제를 잘 이해하는게 가장 중요한 문제였다!