[LeetCode] 1846. Maximum Element After Decreasing and Rearranging

https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/description/

Maximum Element After Decreasing and Rearranging - LeetCode

leetcode - Maximum Element After Decreasing and Rearranging

문제 유형 : 정렬

문제 난이도 : Medium

 

문제

You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:

• The value of the first element in arr must be 1.
• The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

There are 2 types of operations that you can perform any number of times:

• Decrease the value of any element of arr to a smaller positive integer.
• Rearrange the elements of arr to be in any order.

Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

 

당신은 양의 정수배열 arr을 가지고 있다.

몇 변의 정해진 연산을 하여 조건을 맞추어라.

 

조건

- 배열의 첫 번째 요소는 1이어야 한다.

- 두 인접한 요소들 간의 값의 차는 1 이하여야 한다.

 

당신은 배열에 대하여 두 가지 연산이 가능하다.

1. 정수의 값을 자신보다 작게 만들기

2. 배열을 어느 순서로든 재배열 하기

 

조건에 맞게 배열을 바꾸는 연산을 수행한 후, 배열의 가장 큰 값을 반환하라.

 

 

풀이

배열을 비내림차순으로 정렬해준 뒤, 인덱스 0의 값을 1로 바꾼다.

배열을 인덱스1부터 순회하면서 arr[i]가 arr[i-1]보다 1이 초과하게 크면,

arr[i] = arr[i-1]+1을 대입한다.

arr[n-1]을 반환하면 된다.

 

코드

C++

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        const int n = arr.size();

        sort(arr.begin(), arr.end());
        arr[0] = 1;
        for(int i = 1; i < n; i++) {
            if(arr[i]-arr[i-1] > 1) {
                arr[i] = arr[i-1]+1;
            }
        }

        return arr[n-1];
    }
};