[Swift 알고리즘] Codility lesson3 - PermMissingElem

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

쉬운 문제를 연달아 푸니까 자신감도 생기고 좋네여! ㅋㅋㅋ

 

이번 문제는 주어진 [Int]가 1 ~ N+1 의 원소를 가지는데 딱 하나의 원소가 빠져있고 그 원소를 찾는 문제였습니다.

단순하게 생각한다면 배열을 받아서 해당 배열의 크기만큼 하나씩 보고 어떤게 빠졌는지 체크하는것 이겠지만!!

주제를 생각해야겠죠?

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 {
    let a = A.count + 1
    var sum = a * (a + 1) / 2

    A.forEach {
        sum -= $0
    }

    return sum
}

시간 복잡도의 제일 많이 예시로 나오는 1~n 까지의 모든 수의 합을 구하는 방법을 이용했습니다.

옛~~날에 문제적 남자인가에서 비슷한 문제가 나온적이 있는게 기억납니다. (뭐 1~1000? 사이에 한개를 빼놓고 불러주는데 필기를 하지 않고 빠진 숫자를 알아내는 방법)

n * (n + 1) / 2 는 은근히 정말 많이 쓰이니까 까묵지 마세요!