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

 

 

 

 

 

🍄 코딩테스트 문제 풀이

✍🏻 문제 풀이 github 링크

 

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

 

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

 

입출력 예

elements	result
[7,9,1,1,4]	18

 

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ elements:[Int]) -> Int {
    
    var sumElements = [Int]()
    
    for num in 0..<elements.count {
        var some = 0
        for i in 0..<elements.count-1 {
            some += elements[(num + i)%elements.count]
            sumElements.append(some)
        }
    }
    sumElements.append(elements.reduce(0){$0 + $1})
    
    return Set(sumElements).count
}

5개의 숫자로 시뮬레이션을 돌려보니 5개의 숫자를 모두 합하는 것을 제외하고는 자기 자신을 기준으로 1, (1,2), (1,2,3), (1,2,3,4) 로 더해지면, for문을 두 번만 돌리고 끝낼 수 있겠다고 생각을 했다. 돌리는 중의 반복되는 값은 생각하지 않고 마지막에 Set으로 중복값을 빼주어야 겠다고 생각을 했다. 원형이기 때문에 자기 자신을 기준으로 3번째 뒤의 수는 4번째 뒤의 수를 얻을 수 있도록 나머지 연산자를 사용했다. 마지막엔 5개를 모두 더해주는 값을 넣어주었다.

위의 경우를 n개의 수로 일반화하여 풀었더니 한번에 풀렸다! 너무 기분 좋고!

 

 

다른 사람 풀이

import Foundation

func solution(_ elements:[Int]) -> Int {
    var answer = Set<Int>()

    func dfs(_ now: Int, _ num: Int, _ count: Int) {
        answer.insert(num)
        if elements.count == count { return }

        for i in now..<now+1 {
            dfs((i + 1) % elements.count, num + elements[i % elements.count], count + 1)
        }
    }

    for i in 0..<elements.count {
        dfs((i + 1) % elements.count , elements[i], 1)
    }

    return answer.count
}

 

dfs 문제로도 풀 수 있구나?!

dfs 란? 깊이우선탐색 ( depth First Search )의 줄임말로, 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법이다.

dfs에 대한 로직을 구현해본적이 없어서 이번에는 눈으로만 익혀봤는데, 제대로 개념 공부해서 dfs 관련 문제들을 꼭 풀어봐야겠다라는 생각을 했다.