2월 6일 TIL

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

Github 링크

• 이 문제는 주어진 원형 수열의 연속 부분 수열 합으로 만들 수 있는 개수를 return를 요구하는 문제다.
• 우선 원형 수열이랑 일반적인 Array는 0...Array.count-1로 구성되어 있지만, 원형 수열은 마지막 인덱스 다음은 다시 시작 인덱스로 연결이 되어 있는 수열이다.
• 내가 첫번재로 시도한 방법은, 수열을 복사해서 두개를 붙이는것이다. 근데 이 방법은 마지막 두개의 테스트케이스에서 시간초과가 나온다. 아마 이유는 수열의 길이가 최대 1000이며, 두개를 합치면 2000이고, 이중 for 문으로 전체를 다 돌기때문에 시간초과가 뜨는것 같다.
• 그래서 두번째로 시도한 방법은 수동적으로 array.count 초과하는것들은 예외처리 해주는것이다. 여기서 내가 처음에 시도한것의 문제점은 수열의 길이대로 하나하나 추가를 시도했다는것이다. 즉 나는 수열이 1, 2, 3... 이런식으로 찾았는데, 이렇게 찾다보니깐 시간초과도 되고 비효율적이라는것을 알게 되었다.
• 그래서 온라인을 검색하다가 다른분들 풀었던 방법을 찾아보니, 굳이 수열의 길이의 집착할 필요가 없고, for문을 돌면서 하나하나 추가하고, 추가할때마다 set에 추가를 해주면 되는것이다. 즉 다시 말하자면 index 0 부터 시작해서, index + offset 식으로 반복하고, elements[index+offset]을 매번 sum에 추가를 하고, 그러면 자연스럽게 index 0 부터 수열의 길이가 1 ... offset까지 추가가 된다.

import Foundation

func solution(_ elements:[Int]) -> Int {
    var ans = Set<Int>()
    for index in 0..<elements.count {
        var num = 0
        for offset in 0..<elements.count {
            let validIndex = (index + offset) % elements.count
            num += elements[validIndex]
            ans.insert(num)
        }
    }
    return ans.count
}

• 그리고 프로그래머스 컴파일러가 정말 이상한게, 똑같은 코드를 돌려도 어쩔때는 시간초과가 뜨고, 어쩔떄는 정상적으로 작동한다..