[Algorithm] Greedy - ‘곱하기 혹은 더하기’

📣 학습한 내용을 정리한 글입니다.

Greedy Algorithm 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때,
왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘X’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

여러개의 숫자로 구성된 하나의 문자열 S가 입력된다.(1 <= S의 길이 <= 20)

출력

주어진 연산자를 이용해 만들어질 수 있는 가장 큰 수를 출력한다.

문제 풀이

---

Greedy Algorithm 참고내용

• 일반적인 상황에서 Greedy Algorithm은 최적의 해를 보장할 수 없을 때가 많다.
  
• 하지만 Coding Test에선 일반적으로 Greedy Algorithm문제에서 이를 사용해 얻은 해가 최적의 해가 되는 경우가 많다.
  위 참고사항을 준수하며, 풀어보자.
  

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 영상

---