[이코테-그리디-기출] 곱하기 혹은 더하기 (Java)

제한 조건

• 풀이시간 : 30분
• 시간 제한 : 1초

문제

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

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

입력 조건

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

출력 조건

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

예시

입력	출력
02984	576
567	210

풀이

정렬 없이 들어오는 숫자 순서대로 연산하여 가장 큰 수를 만드는 법은 간단하다.
0과 1은 덧셈을 하고 나머지는 모두 곱하면 된다.

이 풀이는 O(N)의 시간 복잡도를 가지며, 단순히 최대 길이 20의 문자열을 하나씩 처리하면 되므로 제한 조건에 걸리지 않는다.

코드

• 코드
• 테스트 케이스