230302 프로그래머스 연속 부분 수열 합의 개수

매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅

프로그래머스 연속 부분 수열 합의 개수 자바, 자바스크립트.

지난번에 풀려고 했다가 너무 집중도 안돼서 집어치워! 하고 던져버렸던 문제인데 괜히 찜찜해서 다시 펼쳐들었다.

마음을 좀 가라앉히고 보니 문제 자체가 어려운 건 아니었던 것 같고,
다른 사람들의 풀이를 통해 '슬라이딩 윈도우 알고리즘'이라는 새로운 부분도 접하게 되었다.

그리고 마지막으로 무릎을 탁 치는 풀이도 보게 되었는데, 사실 어렵게 생각할 것 없이. 그게 효율적이건 아니건을 떠나 뒤에다가 같은 배열을 하나 더 붙여주면 될 일이었다. 뭘 그리 어렵게 생각하고 있었는지...

좋지않은 경험이 여전히 발목을 잡고있는 기분인데 살면서 어떻게 성공하는 경험만 할 수 있겠나 싶으면서도 왜 이 분야에서 벌어지는 경험은 이렇게나 유효타가 강력한건지 모르겠다~!

---

문제 링크

연속 부분 수열 합의 개수

---

Java

정말 오랜만에 자바로 푸는 느낌. 지난번에도 그랬었던 것 같다.
우선 메인 언어를 자바스크립트로 잡았기에 자바의 경우
(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();
    }
}

---

JavaScript

알고리즘 내용은 이 분 블로그를 참고하면서 도움을 받았다.
정리가 정말 잘 돼있는듯. 윈도우 슬라이딩 뿐만 아니라 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;
}

간혹 비슷한 문제를 며칠 연속으로 풀게되는 때가 있는데 관련 문제가 나온다면, 특히 부분수열 처럼 '범위가 정해져 있는' 배열에 대한 연속합을 구하게 되는 문제가 나온다면 윈도우 슬라이딩 알고리즘은 한번 더 연습 해보고 싶다.