[Swift 알고리즘] Codility - FrogRiverOne

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - FrogRiverOne" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

FrogRiverOne coding task - Learn to Code - Codility

 

풀이

이번 문제는 1~X가 모두 나오는 최소 시간을 구하는 문제입니다.

 

저는 Set을 이용해 풀었습니다.

배열 원소의 범위가 1~X이기 때문에 가능했던 풀이 방법인데요.

Set에 num을 넣으면서 Set의 count가 X개라면 1~X의 모든 수가 들어있는 것이죠.

 

문제를 해결하는데는 10분 안으로 끝냈지만 혹시 뭔가 놓친 테스트 케이스가 있을까? 고민하는데

조금 더 시간을 투자했네요.

확실히 코딜리티를 시작하며 고민하는 습관이 길러진 것 같습니다.

범위가 달랐다면?

만약 배열 원소의 범위가 X까지가 아니었다면 하나씩 count를 했어야 하지 않나 싶네요.

배열 길이 범위가 최대 10만이라 O(N)으로 풀어야 하는데

이런 경우에는 배열에 index를 저장하면서 마지막에 다시 한 번 반복문을 돌려 검사하는 방법 뿐인가? 싶습니다.

혹시 좋은 방법 아시는 분 공유 부탁 드립니다.

 

+) 포스팅을 쓰고 번뜩인 아이디어는 X보다 큰 값은 넣지 않는 방법입니다.

유효하게 동작할 것 같네요! ㅎㅎㅎ

 

전체 코드

import Foundation

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    guard !A.isEmpty else { return -1 } //비어있는 배열은 존재할 수 없다.
    guard A.count >= X else { return -1 } //A의 개수가 X보다 작다면 절대 건너지 못한다.

    var leaves: Set<Int> = []
    var result = -1
    for (i, num) in A.enumerated() {
        leaves.insert(num)
        if leaves.count == X {
            result = i //index가 초임
            break
        }
    }

    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.