[이것이 코딩 테스트다 with Java] 그리디 예제 - 곱하기 혹은 더하기

곱하기 혹은 더하기

난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 Facebook 인터뷰

각 자리가 숫자(0부터 9)로만 이루어진 문자열을 사용자로부터 입력받아, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 곱하기(x) 혹은 더하기(+) 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.
단, + 보다 x 를 먼저 계산하는 일반적인 방식과 달리 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) x 9) x 8) x 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

입력 조건

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

출력 조건

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

입력/출력 예시

입력 예시	출력 예시
02984	576
567	210

요점

• 일반적으로 더하기보다는 곱하기가 수를 크게 만드는 방법이다.
• 단 0 또는 1에 대한 연산일 경우 곱하기 보다 더하기가 더 큰 수를 만든다는 예외가 있다.

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int result = 0;
		String numStr = scan.nextLine();
		
		for(char c : numStr.toCharArray()){
			int num = c - '0';
			
			if(num <= 1 || result <= 1){
				result += num;
			}else{
				result *= num;
			}
		}
		
		System.out.println("result = " + result);
	}
}

 

문제 풀이 후기

다른 그리디 문제에 비해 바로 아이디어를 생각하고 코드를 작성할 수 있었다. 다른 그리디 문제로 인해 짓밟힌 자신감에 한줄기 단비 같은 존재ㅜㅜ

 

GitHub: https://github.com/Leeyeonjae/coding-test/blob/main/11_Greedy_Example/11_2_multiplyOrAdd.java

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈