[탐욕법] 난이도1, Facebook 인터뷰 '곱하기 혹은 더하기' (Python)

<문제>

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

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2)*9)*8)*4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

<입력 조건>

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

<출력 조건>

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

---

<문제 풀이>

1. 숫자가 0 또는 1일 경우에는 +연산을, 나머지 숫자는 x 연산을 하는 것이 최댓값을 만들 수 있다.
2. 순서대로 연산을 진행한다고 했으므로 맨 처음 두 개의 숫자를 계산하고 나머지 숫자를 차례대로 하나씩 연산한다.

<코드>

'''입력 예시
02984

567
'''

s = input()
def op(a,b):
    if a==0 or a==1 or b==0 or b==1:
        return a+b
    else:
        return a*b
answer = op(int(s[0]),int(s[1]))
for i in s[2:]:
    answer = op(answer,int(i))
    
print(answer)

 

<고쳐야 할 점>

• 0뿐만 아니라 1인 경우에도 + 연산을 해야 최댓값을 만들 수 있음
• 복습 알고리즘