시간복잡도를 고려한 알고리즘 (2)

아래 문제는 코딜리티에서 제공하는 permMissingElem의 문제입니다🧑🏻‍💻

문제 제시
An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Write a function:
public func solution(_ A : inout [Int]) -> Int

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let n = A.count
    let correctSum = (n + 1) * (n + 2) / 2
    
    let emptySum = A.reduce(0) {
        $0 + $1
    }
    
    return correctSum - emptySum
}

사용된 개념

 - 고차함수(reduce)

문제 뒷담화

해당 문제는 시간 복잡도를 충분히 생각해볼 수 있는 문제였다.

문제 자체는 간단하다. N개의 정수가 주어지고 1부터 N+1까지의 정수가 오는데,

그 사이 혹은 앞이나 맨 뒤에서 하나의 정수가 빠졌을때 어떤 정수가 빠졌는지를 구하는 문제이다.

먼저 처음 접근했던 방식이 아래와 같았다.

<시간 복잡도를 고려하지 못한 방식>

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let max = A.max()!

    for i in 0..<(max+1) {
        if !(A.contains(i + 1)) {
            return (i+1)
        }
    }

    return 0
}

이렇게 하면 통과는 하지만 히든 테스트케이스에서 60% 밖에 달성을 하지 못하였다.

분석해보니 위와 같은 코드는 시간 복잡도가 O(n^)이다.

즉, 모든 배열을 돌면서 조건을 비교하게 됨으로 최악의 경우 O(n)의 시간 복잡도를 갖는다.

그래서 위의 해결된 코드로 수정하였다.

먼저 빈 정수를 찾기전 1부터 N+1까지의 정수의 합은 항상 일정하다.

원래 1부터 N까지의 정수의 합을 구하는 공식은( N * N+1) / 2이다.

그렇지만 이 문제에서는 N+1까지 있으니 위와 같이 N+1을 기준으로 삼고 올바르게 다 들어왔을때의 합을 상수에 할당한다.

그리고 주어진 배열을 reduce 고차함수를 사용해 합을 구해준다.

그리고 두 합의 차를 반환해주면 빠진 정수를 찾을 수 있다.

위와 같이 돌면 시간 복잡도는 O(n)이 될 수 있다.

 

[참고자료]

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility