[이코테] 곱하기 혹은 더하기

1. 문제 정보

• 교재: [이것이 코딩테스트다 with 파이썬] Chap11 그리디 Q02문제
• 문제명: 곱하기 혹은 더하기
• 기출: Facebook 인터뷰

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

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

---

• 입력 조건

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

• 출력 조건

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

---

• 입력 예시1

02984

• 출력 예시1

576

• 입력 예시2

567

• 출력 예시2

210

2. 문제 해결

일반적인 사칙연산의 순서가 아닌 왼쪽에서부터 순서대로 연산이 이루어지기 때문에, 왼쪽에서부터 매 연산마다 가장 큰 결과값을 도출해내는 것이 핵심 아이디어이다.

문자열 S의 각 자릿수는 0 ~ 9이고 더하기와 곱하기만 이용하기 때문에, 다음과 같은 알고리즘으로 매 순간 가장 큰 결과를 도출하는 연산을 선택 후 그 결과값을 저장해나가는 방식으로 구현했다.

1. 두 수 중에서 0 또는 1이 포함된 경우 더하기를 수행한다.
2. 그 외에 경우 곱하기를 수행한다.

3. 나의 코드

# 입력받은 두 정수에 대하여 더하기와 곱하기 연산 결과 중 더 큰 값을 반환
def calc(num1, num2):
    # 두 정수 중 하나라도 0 또는 1인 경우 덧셈 연산 수행
    if num1 in [0, 1] or num2 in [0, 1]:
        return num1 + num2
    # 곱셈 연산 수행
    return num1 * num2

S = list(map(int, input()))  # 입력된 숫자정보

answer = S[0]  # S의 길이가 1인 경우 S가 정답
for i in range(1, len(S)):
    answer = calc(answer, S[i])

print(answer)  # 결과 출력

4. 다른 풀이

그런데 수행할 연산을 굳이 선택할 필요없이 더하기 결과값과 곱하기 결과값 중 더 큰 값을 리턴하는 방식으로 구현하는 것도 직관적인 풀이라고 생각한다.

# 입력받은 두 정수에 대하여 더하기와 곱하기 연산 결과 중 더 큰 값을 반환
def calc(num1, num2):
    return max(num1 + num2, num1 * num2)

S = list(map(int, input()))  # 입력된 숫자정보

answer = S[0]  # S의 길이가 1인 경우 S가 정답
for i in range(1, len(S)):
    answer = calc(answer, S[i])

print(answer)  # 결과 출력