[이것이 취업을 위한 코딩테스트다] 그리디 알고리즘 - 곱하기 혹은 더하기

 

문제 

 

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

 

 

 

해설 코드 

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)

 

 

오답 이유

 

입력된 문자열을 어떤식으로 반복문을 돌려야 하는지 감을 잡지 못하였다. 그리고 입력된 문자열을 배열로 바꿔서 반복문을 돌려야겠다는 생각을 했는데 이는 자바스크립트로 코딩테스트를 공부했다 보니, 파이썬은 문자열에도 index가 존재한다는 것을 까먹었다. 그뿐만 아니라 어떤식으로 곱하기, 더하기 연산자를 사이에 넣어야 하나에 대한 고민을 하다가 문제를 풀지 못하였다. 그리고 두 수 중에서 하나라도 '0' 이거나 '1'일 때 더하기를 수행하는 형식으로 생각하지 않고 문자열 중에서 가장 작은 수 두 개를 골라 이를 더하고 나머지는 곱하는 형식으로 문제를 풀어야겠다고 생각했다. 

 

 

해설 코드 분석

 

해설 코드의 전개 과정은 크게 이렇게 나뉜다. 

1. 입력된 문자열의 가장 첫번째(S[0])를 result값에 넣는다. 
2. 첫 번째 값을 제외한 (두번째 ~ 문자열의 끝까지)를 반복문으로 하나씩 비교하며 이 때 각 비교 원소는 num이 된다.
3. result 값이 1보다 작거나 같거나 num값이 1보다 작거나 같을 때 result = result + num 이 된다. 
4. 그 외의 경우에는 result = result * num 이 된다. 

 

 

깨달은 점

 

-  문자열에도 index가 있다. 무작정 문자열을 배열로 바꾸려고 하지말자. 

-  무작정 코드를 작성하려고 하지말고, 전개 과정을 구체적으로 정한 뒤에 코드를 작성하자.