[C++ 풀이] Codility - Lessons 9 (Maximum slice problem), MaxProfit

 

 

 

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제

 

 

 

 

 

설명

 

배열 A가 주어집니다.

A의 길이는 0 ~ 400,000까지 있으며  A[N]의 각 요소들은 0 ~ 200,000의 값을 지닐 수 있습니다.

 

배열 각 요소별 차가 가장 적은 값을 구하면 되는데 여기서의 범위는 다음과 같습니다.

 

0 <= P <= Q < N.

A[Q] - A[P]의 값 중 두 수의 차가 가장 적은 수를 구하면 되는 문제입니다.

 

한마디로 'A[5] - A[1]' 또는 'A[2] - A[1]' 은 가능하지만 'A[1] - A[5]' 또는 'A[4] - A[8]' 은 불가능 합니다.

 

또 한가지 조건은 두수의 차가 양수가 아니라면 0을 반환해야 합니다.

 

 

 

결과

 

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2)
        return 0;
    
    int result = A[1] - A[0], min = A[0];
    
    for(int i = 1; i < A.size(); i++){
        if(A[i] < min)
            min = A[i];
        else
            result = (result < A[i] - min) ? A[i] - min : result;
    }
    
    if(result < 0)
        return 0;
    else
        return result;
    
}​

 

 

 

https://app.codility.com/demo/results/training2X9KV8-JVE/

 

 

 

이 문제는 최대 값에서 최소 값을 빼주면 되는 문제이지만 한가지 조건 때문에 생각할 것이 좀 많아지게 됩니다.

 

바로 A[Q] - A[P] 조건 때문이죠.

 

즉, 배열 요소에서의 A[i]번째의 요소가 최대 값이자 최소 값이 될 수 있는 녀석입니다.

 

떄문에 이 문제를 풀려면 우선 두수의 차를 구한 후 최솟 값을 찾으면서 A[i]번째 녀석과의 차를 구해주면 됩니다.

 

정리하자면....

 

1. A[Q] - A[P] 조건 때문에 A[i] - min의 값을 계속 구해야 한다.

2. A[i] - min 값들 중 가장 큰 값을 찾으면 된다.

3. min 값은 수시로 변경되므로 계속 찾아줘야 한다.

4. if다음 else if가 아닌 그냥 else로 쓴 이유는 A[i] 번째가 최소값이면 A[i]번째에서는 더이상 값을 구하는 의미가 없기 때문이다.

 

이 글이 이해가 안가시면 직접 수를 넣고 하나씩 돌려보시기 바랍니다.

코드가 짧으니 금방 하실겁니다.!!