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

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

 

 

 

 

 문제 설명

 

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

프로그래머스

 

 

 나의 풀이

 

나머지 연산자를 통해 순회하는 것이 아닌 배열의 크기를 2배로 만든 뒤에 투 포인터를 이용해서 구했다.

하지만 이 풀이는 for문을 두 번 사용하면서 reduce를 사용해서인지 특정 케이스에서 시간초과가 났다.

 

그래서 다른사람의 풀이를 참고했다.

 

import Foundation

func solution(_ elements:[Int]) -> Int {
    var answer: Set<Int> = []
    var arr = [[Int]](repeating: elements, count: 2)
    var flatArr = arr.flatMap{$0}
    let n = elements.count
    
    for i in 0..<n {
        for j in 0..<n {
            answer.insert(flatArr[j..<j+i+1].reduce(0, +))
        }
    }
    
    return answer.count
}

 

 

 

 다른 사람의 풀이

 

1레벨에 숫자 하나만 추가할 수 있게 설정한 DFS이다.

now는 현재 탐색하고있는 숫자이며 이는 1, 2, 3, 4, 5가 있을때 5뒤에는 1이 다시 와야하기 때문에 나머지 연산자로 두었다.

그리고 count == elements.count가 있기 때문에 가장 긴 수열의 합까지 도출할 수 있는 것이다.

예를들어 1, 2, 3, 4, 5의 수열에서 3부터 5의 길이를 갖는 수열을 갖는다고 했을때 3, 4, 5, 1, 2가 될 것이고 이는 count가 5가 될때까지 진행하기 떄문에 도달할 수 있다.

 

투포인터 아니면 for문만 생각했었는데 수열의 길이마다 add한다는 점에서 DFS를 사용하면 시간복잡도를 줄일 수 있는 아이디어가 좋았다.

 

import Foundation

func solution(_ elements:[Int]) -> Int {
    var answer: Set<Int> = []
    
    func DFS(_ now: Int, _ num: Int, _ count: Int) {
        answer.insert(num)
        if count == elements.count { return }
        
        for i in now..<now+1 {
            DFS((i+1) % elements.count, num+elements[i], count+1)
        }
    }
    
    for i in 0..<elements.count {
        DFS((i+1) % elements.count, elements[i], 1)
    }
    return answer.count
    
}