[Swift 알고리즘] 백준 15565 귀여운 라이언

○ ?

투 포인터, 슬라이딩 윈도우 Silver 1

백준 15565 귀여운 라이언

음,, 통과는 되었는데 의문스럽다.

일단 내 답안은 다음과 같은데, n 과 k 의 범위가 1 이상 100만 이하인 상황에서

n번 반복문을 돌며 배열에 append 해주는 게 시간 초과 안뜨고 통과가 된다고..?

테스트 케이스가 문제인건가 🤔

안 될 줄 알았는데 한 번만에 통과가 되긴 했지만 몬가 찝찝하다눙,,

// 122352KB 200ms
let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = nk[0]
let k = nk[1]
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
var lions = [Int]()

for i in 0..<n {
    if input[i] == 1 {
        lions.append(i)
    }
}

if lions.count < k {
    print(-1)
} else {
    var length = 0
    var result = n
    var start = 0, end = k - 1
    while end < lions.count {
        length = lions[end] - lions[start] + 1
        result = min(result, length)
        start += 1
        end += 1
    }
    print(result)
}

 

만약 이걸로 시간초과가 뜬다면 보완해보고자 했던 건

lion 을 아예 100만개로 초기화 해놓고 lion count 를 갱신하면서 해당 index에 값을 넣어주고 마지막 count로 두번째 로직을 실행하는 것. 이렇게 하면 lions 배열을 따로 메모리에 할당할 필요 없이, 변수 하나만 추가하고 처음 받은 input 배열을 재사용할 수 있어 좋다.

n, k 그리고 lionsCount 의 값이 커질수록 더 메모리나 시간이 절약될 듯. 

// 122352KB 200ms
let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = nk[0], k = nk[1]
var input = readLine()!.split(separator: " ").compactMap { Int($0) }
var lionsCount = 0

for i in 0..<n {
    if input[i] == 1 {
        input[lionsCount] = i
        lionsCount += 1
    }
}

if lionsCount < k {
    print(-1)
} else {
    var length = 0
    var result = n
    var start = 0, end = k - 1
    while end < lionsCount {
        length = input[end] - input[start] + 1
        result = min(result, length)
        start += 1
        end += 1
    }
    print(result)
}

 

근데 딱히 두 문제의 시간에 큰 차이가 나지는 않더라. 

시간이 오래 걸리는 테스트 케이스가 없는건가..