[Swift 알고리즘] Codility lesson4 - FrogRiverOne

안녕하세요 코코종입니다.

오늘은 lesson4(Counting Elements)에 진입했네요.

 

요번 문제는 0번 자리에 있던 개구리가 X + 1로 건너가고 싶은데
일정 시간에 길의 index에 낙엽이 떨어지고 그 낙엽으로 길이 다 만들어지는(건널수 있는) 최소 시간을 구하는 문제였습니다.

즉, 1 ~ X까지 배열에 한번이라도 낙엽이 다 떨어지는 시간을 구하는 문제였습니다.

또, 만약에 불가능한 경우라면 -1을 리턴하라고 하네요(중간에 비어버리면 건널수 없겠죠?)

 

아마 배열로 해도 될 것 같기는 하지만..! 이전 단원이 시간 복잡도였으니까 최대한 시간복잡도를 줄이려고 노력했습니다.

 

아이디어는 다음과 같습니다. dictionary를 만들고 해당 자리에 낙엽이 떨어지면 값을 생성합니다.(한번도 안떨어지면 nil이겠죠?)

(낙엽이 X+1이하의 값이라면 이라는 조건을 넣었는데 each element of array A is an integer within the range [1..X] 라는 조건이 있었네요 머-쓱...) 단순히 dict[a] = 1로 해주셔도 됩니당.

dict에 저장을 했으면 그때 개구리와 반대편 사이의 거리만큼의 갯수가 저장된건지 확인하면 둘 사이에 낙엽이 꽉꽉 있는지 확인이 가능합니다! (배열이라면 단순히 count를 해도 되겠네요 저는 dictionary라서 keys.count를 했습니다.)

만약 이렇게 끝까지 거쳤는데도 중간에 빈 곳이 있다? -> -1을 리턴!

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // 0에서 시작해서 X + 1에 도착하려면 걸리는 최소시간
    // A[K] = k -> K초에 낙엽이 떨어지는 위치
    var dict: [Int : Int] = [:]

    for i in 0..<A.count {
        let a = A[i] // i초에 떨어진 낙엽 위치
        // print(a)
        if a <= X + 1 {
            dict[a] = 1
        }
        // print(dict)
        
        if dict.keys.count == X {
            return i
        }
    }

    return -1
}

 

아이디어를 떠올리는 것은 어렵지 않았는데요, 처음에 A[K]가 뭔지 이해가 잘 안되는 바람에...(영어라서 그런가봐여) 쬐금 고민을 했습니다! (추가로 맨날 다짐하지만 문제의 조건을 잘 읽읍시당...)