[Swift 알고리즘] Codility lesson4 - MissingInteger

안녕하세요 코코종입니닷

오늘은 lesson4의 마지막! 문제입니다 큐ㅠㅠㅠ

분명 처음에 코딜리티 시작할때는 '뭐야 한달이면 다풀고 남겠네~~' 했는데 어림도 없쥬? 37문제나 남았네요...이제 10문제 푼거였어요 하... 나레기

 

이번 문제는 배열에서 주어진 수 중에서 중간에 빈 가장 작은 양수의 Int를 구하는 문제였습니다.

특이한 점이 있다면 빈 공간이 없다면 제일 큰 수보다 1만큼 큰 수를 return해야하고 배열에는 음수도 있더라구여...

그래서 처음에 풀었을때에는 음수에 대한 처리를 너무 간단하게 생각해서 runTimeErrorr가 발생했답니다.(여러분도 왜일지 생각해보세영)

제 아이디어는 O(N)으로 해야하니까 For문을 최대한 다시 도는 한이 있더라도 O(n*N)을 만들어서 통과하는것이었습니다.

그래서 양수에 대한 등장여부를 배열을 저장하고 다시 그 배열을 돌면서 가장 먼저 등장하지 않은 값을 return하도록 했습니다.

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    var answer: Int = 1
    let maxValue: Int = A.max() ?? 0
    if maxValue < 1 {
        return answer
    }

    var list: [Int] = Array(repeating: 0, count: maxValue+1) // [0, 0, 0 ... 0]
    for a in A {
        list[a-1] = 1
    }

    for i in 0..<list.count {
        if list[i] == 0 {
            answer = i+1
            break
        }
    }

    return answer
}

 

맞왜틀?? 을 반복하다가 음수에 대한 테스트를 해보니까 list[a-1]로 접근하는 경우에 음수에 접근을 해버리는 멍충한짓을 한거였답니닷...(위에 생각해보라고 한거 하셨나요..??)

그래서 A에서 양수만 남겨주도록 filter를 해서 음수에 대한 처리를 해줬습니다.(음수는 다 무시)

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    var answer: Int = 1
    let A = A.filter{ $0 > 0}
    let maxValue: Int = A.max() ?? 0
    if maxValue < 1 {
        return answer
    }

    var list: [Int] = Array(repeating: 0, count: maxValue+1) // [0, 0, 0 ... 0]

    for a in A {
        if a >= 0 {
            list[a-1] = 1
        }
        
    }

    for i in 0..<list.count {
        if list[i] == 0 {
            answer = i+1
            break
        }
    }

    return answer
}

엄청 어려울줄 알았는데 그냥 for문을 주구장창 여러번 돌리면서 했더니 통과했네요! (물론 음수에 대한 처리를 해주고...)

다음에는 다른 챕터로 돌아오겠습니다~