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

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

https://www.codility.com/

 

 

 

 

문제

 

 

 

설명

 

더블 슬라이스라는 키워드를 문제에서 정의 합니다.

 

더블 슬라이스는 (X, Y, Z)로 구성되며

 

X < Y

Y < Z

로 값의 조건이 주어 집니다.

 

A배열의 index중 Y값을 기준으로 왼쪽과 오른쪽으로 나눕니다.

 

Y값은 변경될 수 있으며 X와 Z의 기준도 변경될 수 있습니다.

 

이 과정에서 X ~ Y값중 최대 합과 Y ~ Z값 중 최대 합을 구한 후

 

이 최대합끼리 더했을 때 가장 높은 수를 구하는 문제입니다.

 

그리고 배열의 맨 앞과 맨 끝 값은 제외하며 X,Y,Z가 붙어있을 경우(slice(3,4,5)) 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)
    
    int len = A.size();
    int result = 0;
    vector<int> left_max(len);
    vector<int> right_max(len);
    
    if(A.size() < 4)
        return 0;
    
    for(int i = 1;  i < len - 1; i++)
        left_max[i] = max(left_max[i - 1] + A[i] , 0);
    
    for(int i = len - 1; i > 1; i--)
        right_max[i - 1] = max(right_max[i] + A[i - 1], 0);
        
    for(int i = 1; i < len - 1; i++)    //max값 위치를 i-1, i+1하는 이유는 Y값을 기준으로 더해야 되기 떄문에.
        result = max(left_max[i - 1] + right_max[i + 1], result);
    
    return result;
}

 

 

 

https://app.codility.com/demo/results/training7F5GNS-JRP/

 

 

 

풀이

 

 

 

이 문제는 생각할게 많은 문제입니다.

저도 풀다가 도저히 안풀려서 웹 검색을 했고, 풀이한 코드를 분석하고 왜 이렇게 되는지 몇일 생각했습니다.

 

사실 이 문제는 조건만 알면 간단한 문제입니다.

 

여기서 말하는 조건은 다음과 같습니다.

 

1. X와 Z값은 그 어디든 상관이 없다.

즉, 배열이 A[0] ~ A[100] 까지 있다 하더라도 최대 값을 구하는 과정에 있어서 X또는 Z값이 1이든 10이든 50이되든 상관이 없다는 뜻입니다.

 

 

2. 음수와 양수가 섞여서 나와도 0이하로 안떨어 지면 최대합 구하는대에 신경을 안써도 된다.

예를들어 A[10] = 이 있다고 가정했을 때,

왼쪽과 오른쪽의 최대 합을 구하는 문제이므로 어차피 음수를 다 더해야 한다는 뜻입니다.

 

왜냐하면 Y값을 기준으로 Y값이 -3값의 위치(index = 5)에 있다고 가정한다면

X값은 1 ~ 4 값중 하나가 되는데 문제의 조건상 X ~ Y까지의 최대 합이므로

X 값이 10, 20 딸랑 두개만 더할 수 없다는 뜻입니다. 

X가 1이 되면 1 ~ 4까지의 최대 합을 구해야 하고, 

X가 2가 되면 2 ~ 4까지,

X가 3이면 3~ 4까지.....

 

이런식으로 되기 때문에 결국 음수든 양수든 다 더해줘야 하며 더한 최대합이 0 이하로만 안내려 간다면 상관 없다는 뜻입니다.

Z축도마찬가지 입니다. 

 

결국 최대 합이 음수가 되는 부분을 처리하면 되는데....

 

3. 최대 합이 음수일 경우 0으로 처리한다.

최대합이 음수가 되는 경우의 수는 2가지 입니다.

 

첫째는 시작과 동시에 음수가 나올 경우,

중간에 최대합보다 높은 음수가 나올 경우.

 

시작과 동시에 음수가 나올경우는 다음과 같습니다.

ex1) A[] = {-1, -1, -1, 10, 20, -1, -1, -1, -1}

ex2) A[] =

ex3) A[] = {-1, -1, -1, 2, 3, 4, 5, 6, 7}

 

왼쪽이든 오른쪽이든 양쪽이든 음수가 나오면 해당 부분을 더해주지 않으면됩니다.

따라서 0으로 처리하는 것입니다.

왜 더하지 않아도 되느냐? 바로 조건 2번 때문입니다. X ~ Y, Y ~ Z 값들을 더해줘야 하기 때문에

X쪽이든 Z쪽이든 음수부터 나온다면 0으로 처리해 줘도 된다는 뜻입니다.

• (double slice (3, 4, 5), sum is 0 조건으로 인해서....)

(ex1번 같은 경우 X값을 3으로 두면 되기 때문입니다. 그 앞에 음수들은 볼 필요가 없죠...)

 

그다음은 중간에 최대 합 보다 높은 음수가 나올 경우인데,

ex) A[] = { 1, 2, 3, 4, 5, 6, -1000, 1, 2, 3, -1000, 5, 6, 7, 8}

이 경우도 마찬가지로 최대 합이 음수가 되버리면 0으로 바꿔줍니다.

그전 데이터 값은 필요가 없기 때문입니다. X ~ Y, Y ~ Z 합 조건 때문에....

 

만약 최대합은 구한다면 X값은 1부터, Y값은 -1000이 있는 index번호 6번에, Z값은 9번에 배치한다면 최대합을 구할 수 있습니다.

Z값을 10이나 11로 한다면 -1000때문에 최대합이 안되고, X값도 1번이아닌 3이나 4번자리부터 시작한다면 최대 합이 되질 않기 때문입니다.

 

 

4. 위 조건들을 모두 충족시키려면 왼쪽과 오른쪽의 최대합들을 모두 구해놔야 한다.

이게 무슨말이냐면....

이렇게 왼쪽과 오른쪽의 최대 합을 구한 뒤 더했을 때 가장 큰 값을 return해주면 되는 것입니다.

 

그리고 이 문제는 for문의 범위도 신경써야 하고, 왼쪽과 오른쪽 합이 들어갈 위치도 신경써야 합니다.

 

때문에 상당히 까다로운 문제라고 생각합니다.

 

이 글을 읽어도 이해가 안된다면 코드를 한번 계속 돌려보세요... 그래도 안된다면 댓글 ㄱㄱ싱