[Codility] 3. PermMissingElem

Donghee Lee·2022년 3월 16일
0

Algorithm

목록 보기
5/17
post-thumbnail

문제 링크
PermMissingElem

문제 요약
정수 N개를 갖는 배열 A가 주어 졌을 때, A의 각 인덱스는 1에서 N+1사이의 정수를 갖는다.
그러나 이 때 딱 하나의 정수가 누락될 때, 누락된 원소를 찾아라.

요구사항
정수 N의 범위가
N is an integer within the range [0..100,000]
이므로 Time Error에 주의해야 한다.
dict 키/밸류로 허튼짓 했다가 O(N^2)를 맛봤다..ㅎ

우선 1~N+1의 합은 항상 일정
여기서 누락된 수가 있는 배열 A의 요소를 다 더하고 합을 빼면
누락된 수를 구할 수 있다.
생각보다 오래 걸렸는데... 나중에 다시 풀어봐야겠다..

코드

import Foundation
import Glibc


public func solution(_ A : inout [Int]) -> Int {
    var elementCnt = Int()
    var elementSum = Int()
    var aSum = Int()

    elementCnt = A.count
    elementSum = ((elementCnt + 1) * (elementCnt + 2)) / 2 // sum of 1~n+1
    
    A.forEach { item in 
        aSum += item
    }

    return = elementSum - aSum
}
profile
Better than Yesterday

0개의 댓글