https://school.programmers.co.kr/learn/courses/30/lessons/161988
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제는 위의 출처로 들어가 보시면 되겠다..
원래 이 문제를 푼 지는 시간이 좀 지났지만,
이를 어떻게 해설을 해야 할까 고민을 했었다.
푸는 것도 어렵지만, 남이 이해할 수 있도록 해설하는 것 또한 어렵기 때문이고,
머리를 또 굴려야 한다는 일종의 귀차니즘 때문인지, 계속 미루게 되었다.
아무튼, 문제를 차근 차근 한 줄 씩 읽어보며 해석을 해 보자.
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
이를 통해 기존에 어떤 수열이 주어지게 된다면, 이에게 두 가지 종류의 수열, 그러니까 -1부터 시작하는 [-1, 1, -1, ... ] 이나, 1부터 시작하는 수열인 [1, -1, 1, -1, ... ] 이 곱해지는 것을 알 수 있다. 여기서 경우의 수는 두 종류의 수열을 곱하게 되므로, 일단 두 가지 케이스를 계산해야 겠다는 감이 올 수 있겠다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
위를 통해 예시를 알 수 있다. 여기서 예시로 나온 연속 부분 수열의 길이는 [-1, 1, -1]이므로, 3이지만, 실제로는 1이 될 수도 있고, 전체 수열의 길이 만큼 될 수 있다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.
연속 펄스 부분 수열의 합 중 가장 큰 것! 그러니까, 저렇게 펄스 수열을 길이가 1인 것부터 최대치인 것 까지 곱해서 나온 수열의 합 중에서 가장 큰 것을 구하라는 뜻이다.
먼저 [2, 3, -6, 1, 3, -1, 2, 4]인 수열이라면 아마도 다들 쉽게 감이 올 것이다.
[1, -1, 1]인 길이 3인 수열을 [3, -6, 1]에 곱하여 [3, 6, 1]을 만든다.
그리고 3 + 6 + 1 = 10 이므로, 최댓값은 10이 될 것이다.
만약 [1, -1, 1, -1]인 길이 4인 수열을 [3, -6, 1, 3]에 곱하면, [3, 6, 1, -3]이 되고,
3 + 6 + 1 + (-3) = 7이 되므로, 10보다 작은 수 이므로 최댓값이 아니다.
문제는... 제한사항이다.
1 ≤ sequence의 길이 ≤ 500,000
-100,000 ≤ sequence의 원소 ≤ 100,000
sequence의 원소는 정수입니다.
아마 처음에 여러분들 중에 모든 경우의 수를 구한 다음,
이들 중에 최댓값을 산출해내는 방법을 생각하신 분들도 계실 것이다.
그러니까,
sequence의 1번째 항에서 수열 [1] 혹은 [-1]을 곱한 합,
수열 [1, -1] 혹은 [-1, 1]을 곱한 합,
수열 [1, -1, 1] 혹은 [1, -1, 1]을 곱한 합, ...
sequence의 끝 까지 도달하게 된다면,
다시 sequence의 2번째 항에서 이를 반복하고...
이런 방식으로 풀게 된다면,
최대 50만개나 되는 sequence의 경우의 수를 일일이 구하느라
막대한 시간이 걸리고, 이는 분명 제한시간 초과라는 문제에 직면할 것이다.
이를 해결하기 위해서는, 불필요한 계산을 최소화 하는 DP 방식과, 누적합이라는 방식을 이용할 필요가 있다.
1. 누적 합
누적 합은 특정 구간까지의 합을 일일이 구하는 과정을 간소화할 수 있는 방법 중 하나이다.
예를 들어보자. 먼저, [2, 3, -6, 1, 3, -1, 2, 4] 수열을 -1 부터 시작하는 펄스 수열을 곱할 경우,
해당 수열은 다음과 같이 변한다: [-2, 3, 6, 1, -3, -1, -2, 4]
여기서 특정 지점에서 시작하여 임의의 구간까지의 합을 구하기 위해 매번 각 자리를 더하는 방식을 채택할 필요는 없다.
각 자리를 앞에 있던 자리 수의 누적으로 더한 합으로 교체해 보면 다음과 같다.
- 2 = -2
- 2 + 3 = 1
- 2 + 3 + 6 = 7
- 2 + 3 + 6 + 1 = 8
- 2 + 3 + 6 + 1 - 3 = 5
- 2 + 3 + 6 + 1 - 3 - 1 = 4
- 2 + 3 + 6 + 1 - 3 - 1 - 2 = 2
- 2 + 3 + 6 + 1 - 3 - 1 - 2 + 4 = 6
따라서 누적 합으로 수열을 만들면: [-2, 1, 7, 8, 5, 4, 2, 6 ]이 된다.
만약 여기서 기존 수열의 2번째 부터 4번째 수인 3, 6, 1을 더한 합을 구하고 싶다?
그러면, 누적 합 수열의 4번째 수열인 8에 첫 번째 수열인 -2를 빼면 된다.
8 - (-2) = 10
지금이야 3자리의 합이라서 번거롭게 느껴질 수 있지만,
나중에 수 십개의 수열의 합을 구하려고 할 때,
일일이 더하지 않고, 딱 두 개의 수열의 차만 구하면 되므로 시간 절약이 엄청나다!
2. DP
위의 누적 합으로 어느 정도 계산을 간편화 하였다.
그러나..! 아직 연산해야 할 경우의 수는 무수히 많다.
이번에는 이해를 쉽게 하기 위해, 알파벳으로 예를 들겠다.
누적합 수열이 숫자가 아닌 알파벳 A, B, C, D..라고 가정해 보자.
| A | B | C | D | E |
그리고 이를 통해 나올 수 있는 부분 수열의 합을 표로 나타내면 다음과 같다.
| 0 | A | B | C | D | |
| E | E - 0 | E - A | E - B | E - C | E - D |
| D | D - 0 | D - A | D - B | E - C | |
| C | C - 0 | C - A | C - B | ||
| B | B - 0 | B - A | |||
| A | A - 0 |
여기서 제목 행과 제목 열을 뺀 흰색에 나온 수들이 모든 경우의 수 이다.
여기에 있는 경우의 수 중에, 가장 큰 값을 찾아야 한다.
흰 칸의 절반 밖에 채워지지 않는 이유는,
누적 합 수열에서는 자기보다 뒷 수열의 합을 빼는 것과, 자기 자신에서 자신을 빼는 것은 성립되지 않기 때문이다.
간단히 말해서, 두 번째 누적합 수열인 B에서 더 작은 A를 빼면 2번째 수의 값이 나오고,
B에서 0을 빼면 첫 번째 + 두 번째 수의 합이 나오는 반면에,
B보다 나중에 나온 수인 C나 D를 빼면 이는 수열의 합에서 나오는 결과가 아니기 때문이다.
아무튼 이와 같이 저렇게 모든 경우의 수를 구하게 되다보면,
누적 합 수열의 길이가 한 칸 늘어날 수록, 제곱의 절반 정도로 계산량이 기하급수적으로 늘어나게 된다는 문제점이 생긴다.
그러나, 불필요한 계산을 줄일 수 있는 방법이 존재한다!
아래, 표에서 일부 파싱한 도표를 보자.
뭔가 여기서 불필요한 계산을 제거할 낌새가 보이지 않는가..?
그렇다! 모두 같은 수를 뺀다는 점이다!
아래 도표에서는 모두 0을 뺀다.
그 다음 열에서는 모두 A를 뺀다.
| 0 |
| E - 0 |
| D - 0 |
| C - 0 |
| B - 0 |
| A - 0 |
따라서... 굳이 빼지 않고도, 여기 위에서 A~E 중 가장 큰 수를 구하면 해결이 된다.
만약 여기 위에서 가장 큰 수가 C라고 가정해보자.
그럼 여기 위에서 C를 제외한 다른 계산은 할 필요가 없으며,
| 0 | A | B |
| E - 0 | E - A | E - B |
| D - 0 | D - A | D - B |
| C - 0 | C - A | C - B |
| B - 0 | B - A | |
| A - 0 |
다음 위 세 가지 C 가 들어간 열에서도 마찬가지로 C - 0, C - A, C - B 만 계산을 하면 된다.
왜냐하면 저 세 열 중에서 세 가지 항목만이 가장 큰 수임을 보장하기 때문이다.
그럼 C 가 없는 그 다음 열을 어떻게 할까?
C 다음으로 큰 수를 기준으로 나머지를 계산하면 된다!
예시를 들겠다. 먼저, 각 항의 크기가 C > B > A > D > E 라고 가정을 한 다음, 이를 크기 순으로 정렬을 좀 바꾸면...
| C | C - 0 | C - A | C -B | ||
| B | B - 0 | B -A | |||
| A | A - 0 | ||||
| D | D - 0 | D - A | D - B | D - C | |
| E | E - 0 | E - A | E - B | E - C | E - D |
이렇게 된다!
여기서 위의 지표면?에 해당하는 부분만 계산을 하면 나머지는 계산할 필요가 없게 된다.
C - 0, C - A, C - B 를 계산한 다음에, D - C, E - D 까지, 딱 누적 합 수열의 길이 만큼 계산해서,
이들 중 가장 큰 수를 뽑으면 끝!
Javascript로 작성한 코드는 다음과 같다.
좀 코드가 지저분하지만, 양해 부탁 바랍니다..
function solution(sequence) {
//부분 수열의 합을 구한다
var subAddsOne = []; // 1, -1, 1....
var subAddsTwo = []; // -1, 1, -1....
let AddsOne = 0;
let AddsTwo = 0;
var Num = 0;
const length = sequence.length;
sequence.forEach(element => {
Num++;
// 연속 펄스 두 종류를 적용한 부분 수열의 합
if(Num%2==0){ // 짝수라면
AddsOne += -element;
AddsTwo += element;
}else{ // 홀수라면
AddsOne += element;
AddsTwo += -element;
}
subAddsOne.push([AddsOne, length - Num]);
subAddsTwo.push([AddsTwo, length - Num]);
});
function sortArr(arr){
let sortedArr = [];
sortedArr = arr.slice().sort((a,b) => b[0] - a[0]);
return sortedArr;
}
const sortedOne = sortArr(subAddsOne);
const sortedTwo = sortArr(subAddsTwo);
//console.log(subAddsTwo);
function getMax(sortedArr, originalArr){
let max = sortedArr[0][0];
//console.log(max)
const size = sortedArr.length;
let index = 0;
for(let [key1, value1] of sortedArr){
if(index >= size){
//console.log(`총 size인 ${size}만큼 도달하여 중지`);
break;
}
for(i = index; i < originalArr.length; i++){
let key2 = originalArr[i][0]
if(size - value1 - 1 <= index ){
//console.log(`한도는 ${size - value1}으로 중단`);
break;
}
let value = key1 - key2;
index++;
//console.log(`(${key1}) - (${key2}) = ${value} || index는: ${index} `);
if(value > max){
max = value;
}
}
}
//console.log(`정답은: ${max}`);
return max;
}
const answer = Math.max(
getMax(sortedOne, subAddsOne),
getMax(sortedTwo, subAddsTwo)
);
return answer;
}
var sequence = [1, 2, 3, 4, 5];
console.log(solution(sequence));'코딩테스트' 카테고리의 다른 글
| 카카오 블라인드 코딩테스트: 자동완성 문제(Level.4)를 이해하고 풀어보자 (6) | 2025.06.07 |
|---|---|
| 카카오 인턴쉽 문제: 수식 최대화 (2) | 2025.05.11 |
| 코딩테스트: "기능개발" 문제 풀이 및 설명 (0) | 2025.03.01 |
| 코딩테스트: 카카오 기출문제 (n진수 게임)을 풀어보자 (2) | 2025.02.23 |
| 코딩테스트: 깊이/너비 우선 탐색(DFS/BFS)를 풀어보자! (4) | 2025.01.26 |
