[2023-01-14]

Start

Codility는 내가 문제 푸는 과정을 전부 다 저장하는 Task timeline기능을 제공하는데

대부분 다 저런 느낌이다.. 영어라.. 해석하는데 시간을 한바가지 쓰고 좀 이해됐다 싶으면 와다다다다다다다다 푸는 식..

MaxProfit 문제

 

A[P] - A[Q]를 해서 최댓값을 구하는 문제 0 <= P < Q < N이다.

 

1트

로직이 틀렸기 때문에 살펴보다가 해답을 찾았다..는 못찾았다..

 

2트

답을 모르겠어서 마구마구 짜다가 아래와 같은 슬픔에 직면했다..

 

 

처음 내가 생각했던 것은 다음과 같다.

 

1. 다 도는 방법

 

주먹구구로 다 돌면 무조건 maximum값은 구할 수 있다.

문제는 배열의 최대 입력값이 400,000이기 때문에 이중 for문으로 다 돌면 400,000 * 400,000 = 160,000,000,000이기 때문에..

1억에 1초라고 치면.. 1600초가 걸린다...^^

 

2. 조건 체크 + 제일 작은 애를 찾아서 뒤부터 찾아보는 방법

 

일단 0이 나올 수 있는 경우

1. 배열의 크기가 1보다 작거나 같은 경우

2. 배열의 요소가 내림차순이거나 전부 다 같은 값일 경우

 

그 다음 가장 작은 애를 찾는데, 아래와 같이 찾았다.

간단해 보이는 코드였지만.. 큰 뜻이 있었다.

 

앞의 값이 뒤의 값보다 작은 경우 위치를 기억하는 식이었는데, 이 때 등호를 사용하지 않았다.

그 이유는 작은 값이 앞에 있을수록 뒤에 뒤져볼 수 있는 값이 많으니까.. 그렇게 했다..

 

그래서 위와 같이 돌렸을 때가 1트 결과를 낳았다..

 

Codility가 말해줬다. 너처럼 짜면 이러한 경우에서는 어찌할래...

 

[8, 9, 3, 6, 1, 2]

 

거기까진 생각안해봤는두ㅐ...

 

내가 1트에서 짠 코드대로라면 결코 위의 배열에 대해서는 정답이 나올 수가 없다..

 

그래서 위의 예제를 보면서

 

아..! 이거 증가하는 배열에서 최소 위치랑  최대 위치 구해서 최댓값 구하는건가보다?! (하는 생각을 했습니다..?^^)

 

 

...

 

뭐이런 돌대가리가 있는지

 

방금 전까지 본인이 어떤 예제로 로직 짰는지 생각도 못하고 이렇게 바로 걸려들다니..^^

 

다행스럽게도.. 로직 짜다가 아..멍청인가..? 를 깨달았지만..

 

2트와 같은 결과를 얻고 말았다..

Codility의 easy는 바보Saeggeasy..뭐 그런..

 

 

성능 테스트에서 날라갔지만 이건 결코 성능 테스트가 날아간 것이 아닌 그냥..로직이 틀려먹은..것..으로 추정된다..

 

따라서 새로운 방법을 찾아보겠습니다..허허

 

 

답을 찾아봤는데..

제일 작은 값과 제일 큰 값을 빼줘야겠다..라고 생각한 것 까지는 똑같은데.. 그걸 구현하는 방법이 다른 것 같아서.. 이해한 것을 적어보자면..

 

일단 인덱스 0값을 최소값을 설정한다.

for문으로 처음부터 돌면서 현재 설정한 최소값보다 작은지 비교한다.

최소값보다 작으면 해당 값을 최소값으로 변경한다.

 

최소값과 현재 인덱스의 값을 빼면서 최대 profit을 구한다.

MaxSliceSum 문제

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

 

1트

MaxProfit 문제를 풀면서 배운 부분들을 적용해보았는데.. 음수 값이 나와도..다 더했을 때 최댓값이 나올 수가 있다.

 

음수가 나왔을 때 무조건 초기화하는 것이 아니라 조건을 걸어서 초기화할 수 있도록 변경해야할 것 같다.

 

2트

추가한 조건은 위의 네모와 같은데,

음수가 나온 경우 기존에 더했던 결과에 음수를 더했을 때 양수인 경우 계속 값을 이어서 더하도록 했다.

 

 

MaxDoubleSliceSum 문제

 

접근 방식

최댓값이 나오는 slice를 구한 후 그거를 다시 slice하는 식으로..

2번 slice..

 

slice가 굳이 두 개가 나올 필요는 없고..? Triplet 형태로 나오면 되는 거라서..

좀좀따리로 문제를 해결해나가고 있는데..

 

문득 이게 소용이 있나 싶었다..

 

로직 자체는 안 바꾸고 자꾸 조건만 추가하고 있는데.. 애초에 로직이 틀려서 정확도 테스트를 통과할 수 없는 것인데..

 

의미가 있는 건가 싶어서..답을 보기로 했다..

 

부분합을 저장해서 하는 방법을 알게 되었다.

 

직접 코드를 쳐보면서 이해하려고 했는데, 마지막 for문 돌아가는 부분이 이해가 가지 않는다..

Y를 이동시키면서 비교하는 부분이라고 하셨는데..좀 더 봐야할 것 같다..

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Sum {
    public int front = 0;
    public int back = 0;
    
    public String toString() {
        return "front: " + front + ", back: " + back;
    }
}

class Solution {
    public int solution(int[] A) {
        int result = 0;
        int size = A.length;
        int back_index = 0;
        if (size == 3) {
            return result;
        }

        Sum[] sum = new Sum[size];
        for(int i = 0; i < size; i++) {
            sum[i] = new Sum();
        }

        sum[1].front = A[1];
        sum[size - 2].back = A[size - 2];

        for(int i = 2; i < size - 2; i++) {
            sum[i].front = Math.max(A[i], sum[i - 1].front + A[i]);
            
            back_index = size - i - 1;
            sum[back_index].back = Math.max(A[back_index], sum[back_index + 1].back + A[back_index]);
        }

        int front, back, total_sum;
        for(int i = 0; i < size - 2; i++) {
            front = Math.max(0, sum[i].front);
            back = Math.max(0, sum[i + 2].back);
            total_sum = front + back;

            result = Math.max(total_sum, result);
        }

        return result;
    }
}

 

End