<프로그래머스> 연속된 부분 수열의합(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EC%97%B0%EC%86%8D%EB%90%9C%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4%EC%9D%98%20%ED%95%A9

[프로그래머스]

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

 

DP로 하면 다... 될 줄 알았어..!!

하지만 안 뚫리는 문제였고(방법이 있겠지만 나는 혼자서 해결하지 못함) 마지막에는 다른 방법을 알아서 그 쪽으로 해결했다.

 

처음에는 부분 수열의 합이라고 그래서 누적합으로 생각하고 DP로 구현하는 방식을 선택했는데 그 누적합 배열을 반복문 2번을 돌게 되다보니까 시간초과가 당연히 나버리더라

구간을 쪼개봐도 안 되는 걸 보고 이 방법으로는 풀 수 없겠다는 생각이 강해졌다.

처음에는 반복문을 2번 돌려보고 다음에는 contains 함수를 썼다.

그래도 기본 복잡도는 동일했기에 시간 차이만 존재할 뿐 시간초과는 났다.

 

그러다 알게 된 방법이랄까... 이미 알고 있었지만 생각나지 않았던 알고리즘이라고 하는게 맞을 거 같다.

바로 투 포인터다.

포인터만 들으면 사실 팔에 닭살이 돋는 느낌이지만 이건 약간 느낌이 다르다.

배열을 한 번 순회할 때 두 개의 변수를 둬서 조건에 맞춰 움직여 원하는 결과를 얻는 알고리즘이라고 이해하면 편한데

특히 이런 연속 부분 수열의 합에서 사용된다.(그게 떠오르지 않은 나는 뭐지...?)

그 단어를 보고는 금방 방법이 생각나기도 하고 도움을 받아 풀이가 완료되었다.👍

통과하는 시간보고 '왜이리 빨라...?!' 라는 생각이 들었었다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray = intArrayOf(0, sequence.size - 1)
        // 연속 부분 수열의 합을 저장하는 변수
        var sum = sequence[0]
        // 왼쪽 인덱스
        var left = 0
        // 오른쪽 인덱스
        var right = 1

        while (left < right) {
            // 합이 k와 같다면
            if (sum == k) {
                // 인덱스의 차이가 더 작다면
                if (answer[1] - answer[0] > right - 1 - left) {
                    answer[0] = left
                    answer[1] = right - 1
                }
                // 왼쪽 인덱스 + 1 한걸 sum에서 빼기
                sum -= sequence[left++]
            } else if (sum > k) { // 합이 k보다 크다면
                // 왼쪽 인덱스 + 1 한걸 sum에서 빼기
                sum -= sequence[left++]
            } else if (right < sequence.size) { // 오른쪽 인덱스가 배열의 사이즈보다 작다면
                // 오른쪽 인덱스 + 1 한걸 sum에 더하기
                sum += sequence[right++]
            } else {
                break
            }
        }

        return answer
    }
}