그리디 알고리즘(탐욕법) - [문제]곱하기 혹은 더하기
2021. 2. 15. 10:36ㆍFront-end/알고리즘
728x90
반응형
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.
단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
예를 들어, 02984 라는 문자열로 만들 수 있는 가장 큰 수는 ((((0+2)*9)*8)*4) = 576 입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.
난이도 ●○○ / 풀이 시간: 30분 / 시간 제한 : 1초 / 메모리 제한 : 128MB
입력조건: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1<= S의 길이 <= 20)
출력조건: 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
입력예시: 02984 출력예시: 576
입력예시2 : 567 출력예시: 210
<문제해결 아이디어>
- 대부분의 경우 '+' 보다는 'X'가 더 값을 크게 만든다.
- 예를 들어, 5+6 = 11 이고 5*6=30 이다.
- 다만 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기 보다는 더하기를 수행하는 것이 효율적이다.
- 따라서 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱한다.
내가 풀어본 답 - 자바스크립트
function multiplyOrPlus(string){
let numberArray = string.split("");
const result = numberArray.reduce((prev,curr)=>{
prev = parseInt(prev);
curr = parseInt(curr);
if(prev<=1 || curr<=1)
return prev + curr;
else
return prev * curr;
});
return result;
}
console.log(multiplyOrPlus("567"));
728x90
반응형
'Front-end > 알고리즘' 카테고리의 다른 글
[구현 - 시뮬레이션과 완전 탐색] 개요 (0) | 2021.02.16 |
---|---|
그리디 알고리즘(탐욕법) - [문제]모험가 길드 (0) | 2021.02.15 |
그리디 알고리즘(탐욕법) - [문제]1이 될 때까지 (0) | 2021.02.15 |
그리디 알고리즘(탐욕법) - [문제] 거스름돈 (1) | 2021.02.15 |
그리디 알고리즘(탐욕법) - 개요 (0) | 2021.02.15 |