[그리디 알고리즘]곱하기 혹은 더하기

문제설명

여러개의 숫자로 구성된 하나의 문자열 s를 입력받음
왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 'x' 혹은 '+' 연산자를 넣어
만들어질 수 있는 가장 큰 수를 구하시오
단, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정

문제풀이

대부분의 경우 곱하기를 할 때 가 값이 커진다.
처음에는 0이 나올 때만 더하기를 하고 나머지는 다 곱하기를 하는게 가장 큰 수를 만들 수 있다고 생각했었다. 그러나 1인 경우에 곱하기를 하면 그대로인데 더하기를 하면 1이 커진다는 사실을 놓친 것이다.

결국 제대로된 풀이는 1보다 같거나 작으면 더하기를 하고 그 외의 경우에는 곱하기를 해주면 된다.

내코드

s = input("길이가 최대 20인 숫자 문자열입력 : ")

result = int(s[0])

for i in s[1:]:
  if int(i) <=1 or result <=0:
    result += int(i)
  else:
    result *= int(i)

print(result)

잘못된 풀이로 생각하고 있어서 잘 못풀다가 문제풀이 아이디어를 고치고 다시 풀었다.
입력받은 문자열의 첫글자를 result에 대입하고 두번째 글자부터 for문 돌리는 아이디어는 살짝 참고했다...

정답코드

data = input()

#첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
	# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <=1 or result <=1:
    	result += num
    else:
    	result *= num
print(result)	

배운점

첫번째 글자를 result에 대입하고 두번째 글자부터 for문 돌리는 아이디어
(놓치지 말것 !) 입력받은 문자열 숫자로 바꿔줘야 대소비교 할 수 있음

Reference

(이코테 2021 강의 몰아보기)2. 그리디 & 구현