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

 

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

프로그래머스

 

평소 연속 부분 수열 문제는 굉장히 많이 접해봤었다.

이 문제는 최대 범위가 1000으로 짧아서 시간 초과 안 나오겠지? 하는 마음으로 완전탐색을 구현했다.

 

문제에서도 알려주는데, 길이가 1~n(elements.count)개의 부분 수열의 합을 구하면 된다.

반복문을 돌리기 전에 나는 길이 1인 부분 수열의 합과 길이 n인 부분 수열의 합을 먼저 구해서 set에 넣었다.

set을 사용한 이유는 중복을 알아서 걸러주기 때문!

길이 2부터 n-1 까지 모두 체크했다. start는 부분 수열의 시작 원소 인덱스.

원형이므로 인덱스 n-1 다음은 0이어야 한다. 그래서 나는 원소 개수로 나눈 나머지로 인덱스를 정했다.

이 방식을 알고있으면 굉장히 도움이 된다. ^__^

 

func solution(_ elements:[Int]) -> Int {
    var set = Set<Int>()
    elements.forEach{ set.insert($0) }
    set.insert(elements.reduce(0, +))
    for i in 2..<elements.count {
        for start in 0..<elements.count {
            var sum = elements[start]
            for next in start..<start+i-1 {
                sum += elements[(next + 1) % elements.count]
            }
            set.insert(sum)
        }
    }
    return set.count
}

 

딱 보면 알겠지만.. 굉장히 아슬아슬하게 통과했다 흑흑

이럴수록 다른 사람의 코드가 너무 궁금해진다...!!!

 

---

 

elements.forEach{ set.insert($0) }

이렇게 set에 각 원소를 넣어줬는데 사실 Set() 이니셜라이저로 바로 넣을 수도 있다..!!

var result:Set<Int> = Set(elements)

이렇게..!! 정리했었는데 까먹었네..ㅎ..

 

흠 다들 비슷하게 했다! 그중에서도 DFS로 푼 분이 계셨다.

길이가 따라서 DFS를 실시하는데 다음에는 나도 이렇게 풀어봐야지...

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 }
        dfs((now + 1) % elements.count, num + elements[now % elements.count], count + 1)
    }

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

    return answer.count
}

 

사실 처음 봤을 때 헷갈렸다ㅠㅠ 그래도 차근차근 분석해 보기

이 코드는 num에 시작 원소를 넣고 길이가 1개인 것부터 n개인 것까지 진행하고(set에 넣고)

그다음 원소를 num에 넣고 반복하는 방식으로 구현되었다. 

 

 

역시 DFS.. 빠르다...!!

꼭 DFS로 풀도록 노력해야지... 흑흑

아자아자~