[ 이것이 코딩테스트다 ] 곱하기 혹은 더하기 - 그리디 알고리즘

[  이것이 취업을 위한 코딩테스트다 with 파이썬  ] 곱하기 혹은 더하기 _ Python 파이썬

 

" 문제 "

 

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '*' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 *를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰수는 ((((0+2)*9)*8)*4) = 576 입니다.

 

<입력 조건>

첫째 줄에 여러 개의 숫자로 구성도니 하나의 문자열 S가 주어집니다. (1<=S의 길이<=20)

 

<출력 조건>

첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

 

---

" 아이디어 "

 

보통 곱하기와 더하기 중 0이 아닌 이상 무조건 곱하기를 해야 가장 큰 수를 만들 수 있다.

그래서 주어진 배열을 차례대로 돌면서 0을 만났을 때는 더하기를, 그 이외의 수는 곱하기를 하면된다.

이때 result 값이 0일 수도 있으므로 if 문에서 result 와 배열의 원소 모두 필터링해야 한다.

 

---

" 코드 "

s = input()
n = len(s)
result = 0
for i in s:
  if i == "0" or result == 0:
    result += int(i)
  else:
    result *= int(i)
 
print(result)

 

---

" 참고자료 "