[이것이 코딩테스트다] 곱하기 혹은 더하기

🗃️문제 설명

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.

단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 (((( 0 + 2 ) x 9) x 8) x 4) = 576 입니다.

또한, 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

🖥️코드

import sys
input = sys.stdin.readline

number = list(map(int, input().strip()))
result = number[0]

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

🧠아이디어

알고리즘 유형 : Greedy

최대 숫자를 만들기 위해 연산 기호를 적절히 활용할 수 있어야 하는데, 이 때 0과 1을 주의해야 한다.

0의 경우 곱 연산을 취하게 되면 0이 되어버리므로 0의 경우는 무조건 더해주는 방향으로 잡아야 한다.

1의 경우 곱 연산을 취하게 되면 자기 자신이 되어버리므로 1의 경우 역시 무조건 더해주는 방향으로 잡아야 한다.

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 곱하기 혹은 더하기
모범 답안 - 곱하기 혹은 더하기