[그리디/Greedy] 이코테 곱하기 혹은 더하기 (Python / 파이썬)

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디(greedy, 탐욕법) 알고리즘의 곱하기 혹은 더하기 문제는 문자열 S가 주어졌을 때 곱하기 혹은 더하기를 수행하여 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 문제이다.

 

이코테 3장 그리디 곱하기 혹은 더하기 문제 정보

출처

- [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

- https://youtu.be/2zjoKjt97vQ

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

 

곱하기 혹은 더하기 문제 요약

• 각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어진다.
• 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣는다.
• 이때 모든 연산은 왼쪽에서부터 순서대로 이루어진다. (일반적인 +와 x 연산 순서 무시)
• 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S(1 ≤ S의 길이 ≤ 20)가 주어진다.
• 결과적으로 만들어질 수 있는 가장 큰 수를 구한다.
  

문제 풀이 과정

1. 문자열 S를 입력받는다.
2. 첫 번째 문자를 숫자로 변경하여 결과 값에 저장한다.
3. 문자열의 길이-1번 반복하여
4. 결과 값이나 현재 문자의 숫자 둘 중 하나라도 0 또는 1인 경우 더하기를 수행하여 결과 값에 반영한다.
5. 0, 1 이외의 수일 경우 곱하기를 수행하여 결과 값에 반영한다.
6. 결과를 출력한다.

 

코드 및 설명

• S - 입력받은 문자열
• result - 현재까지의 연산 결과 값
• num - 현재 문자를 숫자로 변경한 값

S = input()

result = int(S[0])  # 첫 번째 문자를 숫자로 변경

for i in range(1, len(S)):
    num = int(S[i])  # 현재 문자를 숫자로 변경
    if result <= 1 or num <= 1:  # 계산 할 두 수 중에서 하나라도 0 혹은 1인 경우, 곱하기 대신 더하기 수행
        result += num
    else:
        result *= num

print(result)

---

연산할 두 수 중 하나라도 0 또는 1인 경우 더하기를, 나머지 수는 곱하기를 수행하면 된다. 현재 상태에서 조건에 따라 수행하므로 전형적인 그리디 알고리즘이다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디(greedy, 탐욕법) 알고리즘의 곱하기 혹은 더하기 문제를 파이썬 python으로 풀어보았다.