JAVA 프로그래머스 Lv.3 연속 펄스 부분 수열의 합

 

https://school.programmers.co.kr/learn/courses/30/lessons/161988

---

문제

1. 입력으로 sequence ( 1 <= sequence.length <= 500000, -100000 <= sequence[i].length() <= 100000 )이 입력으로 들어옴.
2. 펄스 수열 [1, -1, 1, -1, ..., -1, 1, -1], [-1, 1 -1, ..., 1, -1, 1] 처럼 1과 -1이 연속적으로 번갈아 나오는 수열.
3. 입력으로 들어온 sequence 수열에 펄스 수열을 곱해 부분 수열의 합 중 가장 큰 것을 return.

---

 

초기 코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        int[] sum = new int[sequence.length];
        int[] result = new int[sequence.length];

        if (sequence.length == 1) {
            answer = Math.abs(sequence[0]);
        } else {
            int maxIndex = 0;

            for (int i = 0; i < sequence.length; i++) {
                if (answer < Math.abs(sequence[i])) {
                    answer = Math.abs(sequence[i]);
                    maxIndex = i;
                }
            }

            sum[maxIndex] = (int) answer;

            if (0 > sequence[maxIndex]) {
                result[maxIndex] = -1;

                for (int j = maxIndex - 1; j >= 0; j--) {
                    if (result[j + 1] == 1) {
                        result[j] = -1;
                    } else {
                        result[j] = 1;
                    }
                    sum[j] = sequence[j] * result[j];
                }
                for (int j = maxIndex + 1; j < sequence.length; j++) {
                    if (result[j - 1] == 1) {
                        result[j] = -1;
                    } else {
                        result[j] = 1;
                    }
                    sum[j] = sequence[j] * result[j];
                }
            } else {
                result[maxIndex] = 1;

                for (int j = maxIndex - 1; j >= 0; j--) {
                    if (result[j + 1] == 1) {
                        result[j] = 1;
                    } else {
                        result[j] = -1;
                    }
                    sum[j] = sequence[j] * result[j];
                }
                for (int j = maxIndex + 1; j < sequence.length; j++) {
                    if (result[j - 1] == 1) {
                        result[j] = 1;
                    } else {
                        result[j] = -1;
                    }
                    sum[j] = sequence[j] * result[j];
                }
            }

            for (int i = 1; i < sequence.length; i++) {
                sum[i] = sum[i - 1] + sum[i];
            }

            for (int i = 0; i < sequence.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (answer < sum[i] - sum[j]) {
                        answer = sum[i] - sum[j];
                    }
                }
            }
        }
        return answer;
    }
}

 

조금 다르지만 같은 내용의 코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        int[] sum = new int[sequence.length];
        int[] result = new int[sequence.length];

        if (sequence.length == 1) {
            answer = Math.abs(sequence[0]);
        } else {
            int maxIndex = 0;

            for (int i = 0; i < sequence.length; i++) {
                if (answer < Math.abs(sequence[i])) {
                    answer = Math.abs(sequence[i]);
                    maxIndex = i;
                }
            }

            if (sequence[maxIndex] < 0) {
                result[maxIndex] = -1;
            } else {
                result[maxIndex] = 1;
            }
            if (maxIndex % 2 == 0) {
                for (int i = 0; i < sequence.length; i++) {
                    if (i % 2 == 0) {
                        result[i] = result[maxIndex];
                    } else {
                        result[i] = -result[maxIndex];
                    }

                    if (i == 0) {
                        sum[i] = sequence[i] * result[i];
                    } else {
                        sum[i] = sequence[i] * result[i] + sum[i - 1];
                    }
                }
            } else {
                for (int i = 0; i < sequence.length; i++) {
                    if (i % 2 == 1) {
                        result[i] = result[maxIndex];
                    } else {
                        result[i] = -result[maxIndex];
                    }

                    if (i == 0) {
                        sum[i] = sequence[i] * result[i];
                    } else {
                        sum[i] = sequence[i] * result[i] + sum[i - 1];
                    }
                }
            }
            
            for (int i = 0; i < sequence.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (answer < sum[i] - sum[j]) {
                        answer = sum[i] - sum[j];
                    }
                }
            }
        }
        return answer;
    }
}

 

실패했으나 어떻게 풀려고 했던 것인지 적어보겠다.

 

sequence 배열 내에서 가장 큰 절댓값을 가진 수를 구하여 해당 위치를 maxIndex로 설정하여 기준이 되도록 하였다.

이후 sequence 배열의 maxIndex 위치에 있는 수를 양수가 되도록 하는 펄스 수열을 만들었다.

sum 배열에 sequence 배열과 펄스 수열을 곱하여 누적합 배열이 되도록 만들었다.

 

최종적으로 누적합 배열인 sum을 반복문을 통해 가장 큰 수를 출력할 수 있도록 했다.

 

이 아이디어에 오류가 있느 것은 알았으나 혹시나 해서 일단 만들어보았는데 잘 되지 않았다.

시간도 오래 걸리고 실패한 것들도 꽤 있어서 다른 방법이 필요한 것 같다.

 

수정한 코드 (실패)

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        int[] sum = new int[sequence.length];
        int[] result = new int[sequence.length];

        if (sequence.length == 1) {
            answer = Math.abs(sequence[0]);
        } else {
            int maxIndex = 0;

            for (int i = 0; i < sequence.length; i++) {
                if (answer < Math.abs(sequence[i])) {
                    answer = Math.abs(sequence[i]);
                    maxIndex = i;
                }
            }

            if (sequence[maxIndex] < 0) {
                result[maxIndex] = -1;
            } else {
                result[maxIndex] = 1;
            }
            if (maxIndex % 2 == 0) {
                for (int i = 0; i < sequence.length; i++) {
                    if (i % 2 == 0) {
                        result[i] = result[maxIndex];
                    } else {
                        result[i] = -result[maxIndex];
                    }

                    if (i == 0) {
                        sum[i] = sequence[i] * result[i];
                    } else {
                        if (sum[i - 1] < sequence[i] * result[i]) {
                            sum[i] = sequence[i] * result[i];
                            if (sum[i] < sum[i - 1] + sum[i]) {
                                sum[i] = sum[i - 1] + sum[i];
                            }
                        } else {
                            if (sum[i] < sum[i - 1] + sequence[i] * result[i]) {
                                sum[i] = sum[i - 1] + sequence[i] * result[i];
                            } else {
                                sum[i] = sum[i - 1];
                            }
                        }
                        if (sum[i] > answer) {
                            answer = sum[i];
                        }
                    }
                }
            } else {
                for (int i = 0; i < sequence.length; i++) {
                    if (i % 2 == 1) {
                        result[i] = result[maxIndex];
                    } else {
                        result[i] = -result[maxIndex];
                    }

                    if (i == 0) {
                        sum[i] = sequence[i] * result[i];
                    } else {
                        if (sum[i - 1] < sequence[i] * result[i]) {
                            sum[i] = sequence[i] * result[i];
                            if (sum[i] < sum[i - 1] + sum[i]) {
                                sum[i] = sum[i - 1] + sum[i];
                            }
                        } else {
                            if (sum[i] < sum[i - 1] + sequence[i] * result[i]) {
                                sum[i] = sum[i - 1] + sequence[i] * result[i];
                            } else {
                                sum[i] = sum[i - 1];
                            }
                        }
                        if (sum[i] > answer) {
                            answer = sum[i];
                        }
                    }
                }
            }
        }
        return answer;
    }
}

 

max 함수를 이용하여 가장 큰 수를 찾아보려고 해봤는데 더 많이 실패가 뜬 걸 보니 방법이 잘못된 것 같다.

가장 큰 수를 이용한다는 방법이 잘못 된 것 같아 다른 방법을 생각해봐야 되겠다.

 

현재 가장 절댓값이 큰 수를 양수로 만드는 방법을 사용하고 있는데 이 방법이 잘못되었다면 지금 사용된 펄스 함수 말고도 다르게 생긴 펄스 함수를 사용하여 그쪽에서의 합도 알아봐야 될 것 같다.

 

최종 코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        long[] s1 = new long[sequence.length];
        long[] s2 = new long[sequence.length];

        for (int i = 0; i < sequence.length; i++) {
            s1[i] = sequence[i];
            s2[i] = -sequence[i];
        }

        for (int i = 1; i < sequence.length; i++) {
            s1[i] = Math.max(sequence[i], s2[i - 1] + s1[i]);
            s2[i] = Math.max(-sequence[i], s1[i - 1] + s2[i]);
        }

        for (int i = 0; i < sequence.length; i++) {
            answer = Math.max(answer, s1[i]);
            answer = Math.max(answer, s2[i]);
        }
        
        return answer;
    }
}

 

DP? 문제 인 것 같다.

시간 제한이 없으면 누적합으로 풀어도 될 것 같다.

 

이 문제는 일단 하나의 펄스 함수가 아닌 두 개의 펄수 함수를 계산하며 비교하는 것이 포인트인 것 같다.

 

일단 두 가지로 나누어 계산을 해야 되기 때문에 두 개의 빈 배열을 준비했다.

여기서는 여러 방법이 있겠지만 내가 한 방법은 기존 배열과 기존 배열에 -1을 곱한 배열을 번갈아가며 수를 얻어내 곱하는 것이었다.

 

사실 다른 부분이나 아이디어는 다 내가 생각했지만 중간 반복문은 다른 분들의 힘을 좀 빌렸다...

사실 저게 핵심이긴 하지만 DP 문제를 푸는 게 쉽지가 않다.

다른 분들과 거의 비슷한 구조로 저 반복문을 완성하긴 했는데 각 배열에 다른 배열의 수를 불러와 비교한다는 것이 생각해내기 쉽지 않았다.

 

사실 저 코드는 더 많이 압축할 수 있는 코드인데 내가 알아보려고 조금 늘려놨다.

DP 문제를 더 많이 풀어봐야 될 것 같다.

 

DP 문제는 사실... 좀 어려운 수학 문제 같이 느껴져서 쉽지 않은 것 같다.