코딩테스트 연습 - 연속 부분 수열 합의 개수

문제 풀이 아이디어

문제 이해하기

문제에서 제시한 원형 수열과 연속 수열의 개념을 먼저 이해해야 합니다. 원형 수열은 문제의 그림처럼 수열이 원형으로 표현한 것입니다. 특정한 시작과 끝이 없는 것이 특징입니다. 연속 수열의 경우 원형 수열의 특정 부분에서 특정 부분까지 연속되는 숫자를 나열한 수열입니다.

원형 수열 위에서 숫자를 나열하는 것이므로 원형 수열의 순서를 지켜야 합니다. 문제에 주어진 예시인 [7,9,1,1,4]를 보면 7에서 4로 끝나는데요. 이 원형 수열로 연속 수열을 만드는 경우 4 다음에 다시 시작점인 7이 와서 [4, 7] 같은 수열을 만들 수 있습니다. 하지만 이 원형 수열의 순서를 지켜야 하므로 [7, 4]와 같은 수열은 만들 수 없습니다. 중간에 [9, 1, 1]을 뛰어넘을 수 없기 때문입니다.

따라서 이 문제는 조합으로는 풀 수 없습니다. 조합은 임의의 2개의 숫자를 뽑으므로 원형 수열의 순서를 지킬 수 없기 때문입니다. 따라서 원형 수열에서 i번째 숫자에서 시작하는 l의 길이를 가지는 연속 수열을 만들 때는 원형 수열의 i번째 수에서 순서대로 l개의 숫자를 뽑아야 합니다.

원형을 직선으로 표현하기

하지만 문제는 i + l이 원형 수열의 길이를 넘는 경우입니다. (index out of range) 이 경우에 원형 수열의 첫 숫자로 다시 돌아가야 합니다.

이 부분을 처리하는 방법은 단순합니다. 바로 Array로 주어진 원형 수열의 뒤에 같은 Array를 붙이는 것입니다. 그러면 자연스럽게 i + l이 원형 수열의 길이를 넘어도 원형 수열의 첫 숫자로 돌아가서 연속 수열을 만들 수 있습니다.

이 문제의 경우 연속 수열의 최대 길이가 원형 수열의 길이와 같으므로 2개의 Array를 연속해서 붙이면 됩니다. 길이가 좀 더 긴 연속 수열을 구할 때는 그만큼 더 Array를 붙이면 되겠지요.

이는 원형의 자료를 직선의 자료형으로 표현하는 가장 기본적인 방법입니다.

코드

ArraySlice를 활용하는 방법

연속 수열을 만들기 위해서는 Array의 특정 구간을 떼어내서 만들어야 합니다. Array를 특정 구간을 떼어내는 가장 간단한 방법은 subscript를 활용해서 ArraySlice를 만드는 방법입니다.

하지만 Swift에서 ArraySlice를 사용하는 비용은 큽니다. 이런 코드를 제출할 경우 시간초과가 뜨게 됩니다.

func solution(_ elements:[Int]) -> Int {
    let cnt = elements.count //👉 원형 수열의 길이
    let round = elements + elements //👉 원형 자료구조일 때 쉽게 index out of range 피하는 방법
    var result = Set<Int>() //👉 중복 제거를 위한 Set
		
		// 1 ~ cnt의 길이의 연속 수열을 구한다.
    for l in 1...cnt {
				// 원형 수열의 i번째 숫자에서 연속 수열 시작
        for i in 0..<cnt {
						// i에서 시작해서 길이가 l인 수열의 합 구하기
            result.insert(round[i..<(i + l)].reduce(0, +))
        }
    }

    return result.count
}

ArraySlice를 사용하지 않은 풀이

ArraySlice 대신에 반복문을 하나 더 사용해서 구해보도록 하겠습니다. 삼중반복문이 거슬리기는 가장 마지막 반복문은 정확히 N번 반복하지는 않으므로 O(N^3)보다는 작을 것입니다.

그리고 연속 수열을 새로운 배열을 만드는 것이 아니라 배열 없이 바로 연속 수열의 합을 구하는 방식으로 메모리에 array를 저장하는 작업이 생략되어 있습니다.

이렇게 하면 시간초과 없이 통과할 수 있습니다. 기본에 통과했던 코드의 실행 속도도 10배 이상 빨라졌습니다.

func solution(_ elements:[Int]) -> Int {
    let cnt = elements.count //👉 원형 수열의 길이
    let round = elements + elements //👉 원형 자료구조일 때 쉽게 index out of range 피하는 방법
    var result = Set<Int>() //👉 중복 제거를 위한 Set

		// 1 ~ cnt의 길이의 연속 수열을 구한다.
    for l in 1...cnt {
				// 원형 수열의 i번째 숫자에서 연속 수열 시작
        for i in 0..<cnt {
						// i부터 시작해서 l개의 숫자 더해서 연속수열의 합 구하기
            var temp = 0
            for j in 0..<l {
                let index = i + j
                temp += round[index]
            }
            result.insert(temp)
        }
    }

    return result.count
}

ArraySlice에 대하여

비록 이 문제에서 ArraySlice를 사용하지 못했지만 array를 활용하는 유용한 방법 중에 하나임에는 분명합니다. Array를 subscript를 통해서 특정 부분만 잘라오면 그 자료는 Array 타입이 아니라 ArraySlice 타입이 됩니다. ArraySlice 타입은 위에서 reduce를, 그리고 아래 예시에서 append를 사용했듯이 대부분의 Array 타입의 메소드를 사용할 수 있습니다.

ArraySlice를 사용하면서 주의할 점은 index를 일반적인 Array처럼 사용하면 안된다는 것입니다. ArraySlice는 별도의 메모리에 값이 저장되는 것이 아니라 원본인 Array를 값을 참조하고 있는 방식입니다. 따라서 별도의 index를 가지는 것이 아니라 Array의 index를 공유합니다. 따라서 [1..<3]의 ArraySlice의 첫번째 index는 일반적인 Array처럼 0이 아니라 1이 됩니다. (0으로 접근하는 경우 index out of range 에러가 납니다.)

ArraySlice는 위처럼 원본인 Array를 강한 참조하고 있습니다. 즉 ArraySlice가 메모리에서 내려가지 않는 한 Array 역시도 메모리에서 내려가지 않습니다. 따라서 실무에서 ArraySlice를 사용할 때는 라이프 사이클이 긴 메소드 내부에서 사용하는 것은 지양해야 합니다.

let array = [7,9,1,1,4]
var arraySlice = array[1..<3]
arraySlice.append(100)

print(type(of: arraySlice)) // ArraySlice<Int>
print(arraySlice) // [9, 1, 100]

print(arraySlice[0]) //🚫 index out of range
print(arraySlice.startIndex) // 1
print(arraySlice[1]) // 9