순회를 최소화한 알고리즘 (2)

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

 

문제 제시

 

This is a demo task.

Write a function:

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

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var compareArr = Set<Int>()
    for item in A {
        if item > 0 {
            compareArr.insert(item)
        }
    }
    
    if compareArr.isEmpty {
        return 1
    }
    
    for (index, _) in compareArr.enumerated() {
        if !(compareArr.contains(index + 1)) {
            return index + 1
        }
    }
    return compareArr.max()! + 1
}

 

사용된 개념

 - 배열 순회

 - 집합

 

문제 뒷담화

해당 문제를 먼저 해석해보자면, 주어진 배열에서 1보다 같거나 큰 양수값 중 빠진 최소한의 양수값을 반환하는 문제이다.

그래서 1,2,3,5가 들어오면 4가 최소로빠졌으니 4를 리턴하고 -1,-2,-3이 들어오면 1이 빠졌으니 1을 리턴하는 문제였다.

먼저 값의 중복을 없애주기위해 compareArr라는 Set 타입의 집합을 만들고 주어진 배열에서 0보다 큰 양수값만 들어갈 수 있도록 

조건문을 돈다.

그 후 비어있다면 1이 빠진 경우이니 바로 1을 리턴해주면된다.

마지막으로 만들어진 Set을 enumerated로 조건을 도는데 조건에서 인덱스의 1만큼 더해준게 해당 데이터 값이 될테니 그 값이 없다면

그것이 빠진값이니 바로 index+1을 리턴해준다.

어떤소리냐면 compareArr에 1,2,4,5 이렇게 4개의 데이터가 들어가있다면, compareArr는 아래와 같이 값을 가질 것이다.

compareArr[0] = 1
compareArr[1] = 2
compareArr[2] = 4
compareArr[3] = 5

그러면 해당 집합배열은 길이가 4이고 최대 데이터의 맥시멈값은 5이다. 즉 미스매칭이 일어난다. 이것을 잡기위해

해당 인덱스를 접근했을때 인덱스 + 1을 한 값이 가지고 있는 데이터값이 아니라면 미스매칭이 일어난것으로 판단할 수 있다.

이렇게 2번째 인덱스에 접근했을때 3을 가지고 있어야하는데 4를 반환하는걸 보면 3이 빠진걸 알 수 있다.

위의 for문 안에 if문은 그걸 잡아주는 로직이다.

그후 마지막으로 모든 요소가 있다면 빠진것은 마지막 맥시멈값 다음값이 될것이다.

간단히 compareArr.max()를 가지고 1 더해주면 된다.

물론 여러번 조건문을 돌거나 compareArr를 A와 다시 비교해주고 하는 작업을 거쳐도 되지만 그럴경우 시간 복잡도가 늘어나게된다.

해당 방법으로 했을때 가장 조건을 돌지 않아 시간복잡도를 만족시킬 수 있었다.

 

[참고자료]

https://app.codility.com/c/run/trainingRYYVDG-K3S/

Codility