[이코테-그리디] 기출 - 02. 곱하기 혹은 더하기

[문제]

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

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

---

[입력 조건]

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

 

[출력 조건]

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

 

<입력 예시>
02984

<출력 예시>
567

---

[내가 푼 풀이]

🔎 아이디어

• 간단하게 입력된 수를 순회하면서 더하는 것이 더 큰지 곱하는 것이 더 큰지 확인하며 더 큰 값을 가지는 경우를 선택하는 방법이 있다.

 

🔎 코드 설계

arr = list(map(int,input()))

init = time.time()
current = arr[0] # 현재 계산 결과

for i in range(1,len(arr)):
  current = max(current+arr[i],current*arr[i]) # 계산 결과가 더 큰 값을 선택

print(current)

 

🔎 단점

• 매번 더하기 연산과 곱하기 연산을 둘다 해야한다.

 

[책 풀이]

🔎 아이디어

• 더하기보다 곱하기가 더 큰 값을 만든다.
• 곱할때 더할때보다 더 작아지는 특수한 경우(곱하는 수에 0이나 1이 있는 경우)를 제외하고 곱하기를 수행하면 된다.

0을 곱하면 0이 되고, 1을 곱하면 자기자신이 되므로 이러한 경우엔 더하는 것이 더 좋다.

 

 

🔎 코드 설계

arr = list(map(int,input()))
init = time.time()
current = arr[0] # 현재 계산 결과를 나타내는 변수

for i in range(1,len(arr)):
  num = arr[i]
  if num <=1 or current <=1: # 곱하는 수에 0이나 1이 있는 경우
    current += num # 더하기
  else:
    current *= num # 특수한 경우를 제외하고 대부분 곱하기를 수행

print(current)

 

---

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬

* 포스팅에 책의 내용과 개인적인 해석이 같이 포함됩니다.