[Java] 연속 펄스 부분 수열의 합 - Lv3 프로그래머스

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

프로그래머스

 

 

첫 풀이

---

역시나 아무생각없이 코드쓰러 돌진했다

class Solution {
    public long solution(int[] sequence) {
        long answer = Integer.MIN_VALUE;
        if(sequence.length == 1) return Math.abs(sequence[0]);
        for(int i=0; i<sequence.length; i++) {
        	long sum1 = 0;
        	long sum2 = 0;
        	for(int j=i; j<sequence.length; j++) {
        		if(j%2==0) {
        			sum1 += sequence[j];
        			sum2 -= sequence[j];
        		}
        		else {
        			sum1 -= sequence[j];
        			sum2 += sequence[j];
        		}
        		answer = Math.max(answer, Math.max(sum1, sum2));
                	if(answer < 0) break;                
        	}
        }
        return answer;
    }    
}

sum1과 sum2변수에 +, -일때의 값을 담았고 음수일 때 초기화시켜주었다.

당연히 가장 큰 값이 양수일 거라 생각했기 때문이다. 과연??

 

무언가 잘못됐다..

1. sequence배열의 길이가 500,000까지고

2. 배열의 길이가 50만인데 이중 반복문 안에 조건문까지 사용했다..(이게 핵심인듯..)

뭔가 시간복잡도를 만족하지 못한 것 같다.

 

코테준비를 하며 계속 시간복잡도 공부를 하고있는데, 개인적으로 독학의 영역이 아닌것 같다는 생각이 자꾸만 든다.. 어디서 인강이라도 듣던지 해야겠다.. 여튼 코드를 뜯어고쳐보자.

 

 

두번째

---

어떻게하면 변수를 최대한 선언하지않고, max메서드 두번이 아니라, 한번만 호출하게 할 수 있을까 생각해봤다.

import java.util.Arrays;

class Solution {
    public long solution(int[] sequence) {
        if(sequence.length == 1) return Math.abs(sequence[0]);
        
        long[] plus = new long[sequence.length];
        long[] minus = new long[sequence.length];
        plus[0] = sequence[0];
        minus[0] = sequence[0]*-1;
        for(int i=1; i<sequence.length; i++) {
        	if(i%2==0) {
        		plus[i] = Math.max(plus[i-1] + sequence[i], sequence[i]);
        		minus[i] = Math.max(minus[i-1] + sequence[i]*-1, sequence[i]*-1);
        	}
        	else {
        		plus[i] = Math.max(plus[i-1] + sequence[i]*-1, sequence[i]*-1);
        		minus[i] = Math.max(minus[i-1] + sequence[i], sequence[i]);
        	}
        }
        
        Arrays.sort(plus);
        Arrays.sort(minus);
        
        return Math.max(plus[sequence.length-1], minus[sequence.length-1]);
        
    }    
}

 

1. 이중for문은 배열을 생성해서 for문 하나로 압축했다.

2. 누적합을 활용하여 펄스수열곱을 적용한 누적합이 값이 현재 배열보다 작다면 초기화를 시켜주었다.

if(i%2==0) {
    plus[i] = Math.max(plus[i-1] + sequence[i], sequence[i]);
    minus[i] = Math.max(minus[i-1] + sequence[i]*-1, sequence[i]*-1);
}
else {
    plus[i] = Math.max(plus[i-1] + sequence[i]*-1, sequence[i]*-1);
    minus[i] = Math.max(minus[i-1] + sequence[i], sequence[i]);
}

 

3. 마무리로 정렬을 통해 첫 펄스 수열값이 1일때와 -1일때의 배열의 max값을 리턴해주었다.