매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅
프로그래머스 연속 부분 수열 합의 개수 자바, 자바스크립트.
지난번에 풀려고 했다가 너무 집중도 안돼서 집어치워! 하고 던져버렸던 문제인데 괜히 찜찜해서 다시 펼쳐들었다.
마음을 좀 가라앉히고 보니 문제 자체가 어려운 건 아니었던 것 같고,
다른 사람들의 풀이를 통해 '슬라이딩 윈도우 알고리즘'이라는 새로운 부분도 접하게 되었다.
그리고 마지막으로 무릎을 탁 치는 풀이도 보게 되었는데, 사실 어렵게 생각할 것 없이. 그게 효율적이건 아니건을 떠나 뒤에다가 같은 배열을 하나 더 붙여주면 될 일이었다. 뭘 그리 어렵게 생각하고 있었는지...
좋지않은 경험이 여전히 발목을 잡고있는 기분인데 살면서 어떻게 성공하는 경험만 할 수 있겠나 싶으면서도 왜 이 분야에서 벌어지는 경험은 이렇게나 유효타가 강력한건지 모르겠다~!
정말 오랜만에 자바로 푸는 느낌. 지난번에도 그랬었던 것 같다.
우선 메인 언어를 자바스크립트로 잡았기에 자바의 경우
(1) 새롭게 알게된 슬라이딩 윈도우 알고리즘으로 풀어보고,
(2) 똑같은 array를 후에 붙여서 답을 구해보는 방식으로 풀었다.
이번 문제는 결국엔 set이 활용되어야 할 것 같아 모든 문제풀이에는 Set 자료구조를 활용했다.
먼저 첫 번째, 슬라이딩 윈도우 알고리즘. for문과 if문 때문에 depth가 너무 깊어진 건 좀 아쉽다.
import java.util.*;
class Solution {
public int solution(int[] elements) {
Set set = new HashSet();
int length = elements.length;
// 원소의 갯수
for (int i = 1; i <= length; i += 1) {
int sum = 0;
for (int j = 0; j < length; j += 1) {
if (j == 0) {
for (int k = 0; k < i; k += 1) {
sum += elements[k];
}
}
if (j != 0) {
sum -= elements[j - 1];
sum += elements[(j + i - 1) % length];
}
set.add(sum);
}
}
return set.size();
}
}
두 번째, array를 복사해서 뒤에 붙인 후에 index 걱정 없이 답 구해보기
import java.util.*;
class Solution {
public int solution(int[] elements) {
Set set = new HashSet();
int length = elements.length;
int[] extended = new int[length * 2];
for (int i = 0; i < length * 2; i += 1) {
if (i < length) {
extended[i] = elements[i];
continue;
}
extended[i] = elements[i - length];
}
// 원소 갯수
for (int i = 1; i <= length; i += 1) {
int sum = 0;
for (int j = 0; j < length; j += 1) {
sum += extended[i + j];
set.add(sum);
}
}
return set.size();
}
}
알고리즘 내용은 이 분 블로그를 참고하면서 도움을 받았다.
정리가 정말 잘 돼있는듯. 윈도우 슬라이딩 뿐만 아니라 Set도 정리를 잘 해두셔서 한 번 읽어보길 추천한다.
먼저 효율성을 내려놓고 말 그대로 모든 경우를 생각해서 더하는 로직.
function calculateSum(array) {
return array.reduce((acc, cur) => acc + cur, 0);
}
function solution(elements) {
const set = new Set();
// 원소 갯수를 i
for (let i = 1; i <= elements.length; i += 1) {
for (let j = 0; j < elements.length; j += 1) {
if (j + i <= elements.length) {
set.add(calculateSum(elements.slice(j, j + i)));
continue;
}
set.add(calculateSum(elements.slice(j))
+ calculateSum(elements.slice(0, j + i - elements.length)));
}
}
return set.size;
}
그리고 윈도우 슬라이딩 알고리즘을 적용.
배열의 누적 덧셈을 하기 위해 for문을 사용할 수도 있기는 한데, depth가 정말 한도 끝도 없이 깊어지는 느낌이라 하나라도 줄여보기 위해 reduce를 사용했다.
function solution(elements) {
const set = new Set();
const subArrayLength = elements.length;
for (let i = 1; i <= subArrayLength; i += 1) {
// 슬라이딩 윈도우
let sum = 0;
for (let j = 0; j < subArrayLength; j += 1) {
if (j === 0) {
sum = elements.slice(0, i).reduce((acc, cur) => acc + cur, 0);
}
if (j !== 0) {
sum -= elements[j - 1];
sum += elements[(j + i - 1) % subArrayLength];
}
set.add(sum);
}
}
return set.size;
}
간혹 비슷한 문제를 며칠 연속으로 풀게되는 때가 있는데 관련 문제가 나온다면, 특히 부분수열 처럼 '범위가 정해져 있는' 배열에 대한 연속합을 구하게 되는 문제가 나온다면 윈도우 슬라이딩 알고리즘은 한번 더 연습 해보고 싶다.