그리디 알고리즘 - 2. 곱하기 혹은 더하기

문제 :

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

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

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

입력 예시 1
02984
출력 예시1
576

입력 예시2
567
출력 예시2
210

구현코드 :

import java.util.*;

public class Main6{
	public static void main(String args[]){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int[] arr = new int[s.length()];
		for(int i = 0 ; i < s.length();i++){
			arr[i] = s.charAt(i) - '0';
		}
		int sum = 0;
		for(int i = 0 ; i < arr.length;i++){
			if(sum == 0) sum += arr[i];
			else {
				if(arr[i] == 0 || arr[i] == 1) sum += arr[i];
				else sum*=arr[i];
			}
		}
		System.out.println(sum);
	}
}

코드 해석 :

이 문제는 더하기를 해야하는 경우, 곱하기를 해야하는 경우를 나눠주면 되는 문제이다. 하지만
이 문제에 한가지 더 생각해야 할 점은 첫 수는 무조건 더해주어야 한다는 점이다.
우선 더하기를 해야하는 경우는 0 ,1 두가지 일 때이다.
그래서 0,1일땐 더해주고 나머지 수일땐 곱해준다. 위에서 이야기했던 첫번째 숫자 더하기는 sum 으로 판단하였다. 만약 sum 이 0이라면 더해주는 것으로 !!!