C++ 1005. Maximize Sum Of Array After K Negations(Leet Code)

Leet Code_1005. Maximize Sum Of Array After K Negations

Greedy

 

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

vector의 원소들을 주어진 횟수만큼 음수, 양수를 바꾸어 최대 합계 구하기

​

방법

1. vector의 원소들을 주어진 횟수만큼 음수, 양수를 바꾸어 최대 합계 구하기

 

결과

vector의 원소들을 주어진 횟수만큼 음수, 양수를 바꾸어 최대 합계 구하기

 

통과한 코드

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& vec, int K) {
    int sum = 0;
    while (K--)
    {
        vector<int>::iterator iter = min_element(vec.begin(), vec.end());
        *iter = -(*iter);
    }
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
        sum += *it;
    return sum;
}
};

vector에서 최소값을 찾아 K번 만큼 값을 바꿔주고 합계를 구했다.

생각보다 문제 해결방법이 바로 생각나서 빨리 푼 문제.

속도는 느리다. 다른 사람 코드를 보니..

 

다른 사람 코드

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& a, int k) {
      int n=a.size();
        sort(a.begin(),a.end());
        int i;
        for(i=0;i<n;i++){
            if(k<=0)break;
            
            if(a[i]<0){
                a[i]=-a[i];
                k--;
            }else{
                break;
            }
        }
        if(k%2==0){
            int sum=0;
            for(int i=0;i<n;i++){
                sum+=a[i];
            }
            return sum;
        }
        else{
            sort(a.begin(),a.end());
            a[0]=-a[0];
        int sum=0;
            for(int i=0;i<n;i++){
                sum+=a[i];
            }
            return sum;
            
        }
    }
};

코드 드럽게 구리네..했는데 빠르다ㅠ

내 코드와 차이점을 보니

나는 K번 만큼 vector에서 min값을 찾아서 처리했고,

다른 사람은 정렬하여 첫번째 값에만 접근하여 값을 바꿔주었다.

1. 음수값이 있는 만큼 다바꿔준다.

2. 양수만 남아있는 상태에서는 짝수면 sum을 구하고(-1 곱하기를 반복하면되니깐)

3. 홀수면 다시 정렬해서 최소값만 한번 -1을 곱하고 sum을 구했다.

코드가 구린게 아니라 똑똑하다잉