[99클럽 코테 스터디 5일차 TIL] 백준 수열 Swift

 

오늘의 문제

- 백준 수열

- https://www.acmicpc.net/problem/2559

 

오늘의 학습 키워드

- N 의 크기와 시간 복잡도

- 투 포인터

 

접근 방법

N 의 크기와 시간 복잡도

- 입력이 2 <= N <= 100,000 이고 1 <= K <= N 이다.

- 단순하게 2차원 반복문으로 배열에서 연속적인 합을 구하게 되면

- 최대 시간 복잡도는 N * N = 00,000,000,000 이 될 수 도 있다. 

 

투 포인터

- 범위를 지정해서 전체 합을 구해야 하는데, 2차원 반복문으로 계산하기에는 시간 복잡도가 크기에 다른 방식을 찾아야 했다.

- 시작, 끝 지점을 계산해놓고, 순서대로 인덱스를 증가시키면서 계산하면 시간 복잡도가 줄어들 수 있다.

 

문제 풀이

// 매일 9시 학교에서 측정한 온도
// 3 -2 -4 -9 0 3 7 13 8 -3
// 연속적인 며칠 동안의 온도의 합이 가장 큰 값은?
// 5일 간의 온도의 합 = [-12, -12, -3, 14, 31, 28]
// 가장 큰 온도의 합 = 31

// N : 온도를 측정한 전체 날짜의 수, 2 <= N <= 100,000 (최대 반복은? N * N = 100,000,000,000)
// K : 합을 구하기 위한 연속적인 날짜의 수, 1 <= K <= N

func findMaxTempSum(_ n: Int, _ k: Int, _ tempArray: [Int]) -> Int {
    var start = 0
    var end = k
    var sum = tempArray[start..<end].reduce(0, +)
    var maxSum = sum

    for _ in 1..<n {
        guard end < n else {
            break
        }

        start += 1
        end += 1

        sum = sum - tempArray[start - 1] + tempArray[end - 1]
        maxSum = max(maxSum, sum)
    }

    return maxSum
}

func readInput() -> (Int, Int, [Int])? {
    guard let input = readLine() else {
        return nil
    }

    let splitedInput = input.split(separator: " ")
    guard let n = Int(splitedInput[0]), let k = Int(splitedInput[1]) else {
        return nil
    }

    let inputArray = readLine()?.split(separator: " ").compactMap { Int($0) } ?? []
    return (n, k, inputArray)
}

if let (n, k, tempArray) = readInput() {
    let result = findMaxTempSum(n, k, tempArray)
    print(result)
}

 

- 초기 코드에서는 guard 구문 이전에 start, end 인덱스를 +1 해줬어서 마지막 값 고려가 어려웠다.

- 테스트 케이스를 아래처럼 했을때, 7이 나와야하는데 5가 나왔었다.

4 2

1 2 3 4

- 위의 테스트 케이스를 통해 마지막 인덱스가 잘못 계산된것을 알게 되었다.

 

오늘의 회고

- 입력의 크기와 구현 방식에 따라 시간 복잡도를 생각해보자.

- 예외 케이스를 고려해보자.