양의 정수 목록이 있다고 가정합니다. 인접한 정수는 부동 소수점 나누기를 수행합니다. 예를 들어 [2,3,4] -> 2 / 3 / 4입니다. 이제 임의의 위치에 괄호를 추가하여 이러한 작업의 우선 순위를 변경할 수 있습니다. 최대 결과를 얻으려면 괄호를 추가하는 방법을 찾아야 하고 문자열 형식에서 해당 표현식을 찾아야 합니다. 표현식에는 중복 괄호가 포함되어서는 안 됩니다. 따라서 입력이 [1000,100,10,2]와 같으면 결과는 "1000/(100/10/2)"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=숫자 배열의 크기
- n이 0이면 빈 문자열을 반환합니다.
- num :=nums[0]을 문자열로
- n이 1이면 num을 반환합니다.
- n이 2이면 num concatenate /를 반환하고 nums[1]을 문자열로 연결
- den :=빈 문자열
- 1 ~ n – 1 범위의 i에 대해
- den :=den + nums[i]를 문자열로
- i가 n – 1이 아니면 den :=den 연결 '/'
- 숫자 연결/연결( den 연결, 연결)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if(n == 0) return "";
string num = to_string(nums[0]);
if(n == 1) return num;
if(n == 2) return num + "/" + to_string(nums[1]);
string den = "";
for(int i = 1; i < n; i++){
den += to_string(nums[i]);
if(i != n - 1) den += "/";
}
return num + "/" + "(" + den + ")";
}
};
main(){
vector<int> v = {1000,100,10,2};
Solution ob;
cout << (ob.optimalDivision(v));
} 입력
[1000,100,10,2]
출력
1000/(100/10/2)