[Swift] - 교집합

스위프트로 투포인터 알고리즘을 구현해보자

1. 문제 설명

무작위로 주어진 두 개의 Int 배열 이 있다. 두 비열의 교집합을 구하라.

2. 나의 풀이

처음에는 아주 간단한 풀이가 떠올랐다.

func solution(_ A: [Int], _ B: [Int]) -> [Int] {
    var ret: [Int] = []
    for i in A {
        if B.contains(i) == true {
            ret.append(i)
        }
    }
    return ret
}

코딩을 처음 접하는 사람들은 이렇게 해답을 낼 것이다. 하지만 알고리즘을 배우기 시작한 이후로 시간을 어떻게 하면 더 줄일 수 있을까..
어떻게하면 불필요한 검색을 줄일 수 있을까 고민하다가
정확한 해답을 찾게됬다.

배열 A 와 B를 sort 해준다.
예로 5, 3, 4, 2 와 2, 7, 8, 5 를 들어보자
sort 해주면
2, 3, 4, 5
2, 5, 7, 8 이 된다.

각각 A[0]와 B[0] 를 비교, 같으면 ret 에 append 해준다.
다음 A[1] 와 B[1] 를 비교. B[1] 이 더 큰 값이 된다.
B[1] 보다 크거나 같아질 때 까지, A[1 + i] 해준다.
A[1 + i] 가 B[1]과 같으면 append 해주고 아니라면 다시, 작은 B[1] 에서 + i 해주며 올린다.

처음에 내가 위에 올린 풀이를 보자.
2가 포함되어있는지 알기 위해 2, 7, 8, 5 를 모두 search 했다.
3이 포함되어있는지 알기 위해 역시 2, 7, 8, 5 를 모두 search 했다.

하지만 시간을 줄인 코드를 보면 ,
모든 값들을 search 하지 않는다.

import Foundation

func solution(_ A: [Int], _ B: [Int]) -> [Int] {
    var ret: [Int] = []
    var a = A.sorted()
    var b = B.sorted()
    var i: Int = 0
    var j: Int = 0
    func D(_ n1: inout Int, _ n2: inout Int) {
        if n1 == a.count || n2 == b.count {
            return 
        }
        if a[n1] == b[n2] {
            ret.append(a[n1])
            n1 += 1
            n2 += 1
            D(&n1, &n2)
        } else if a[n1] > b[n2]{
            n2 += 1
            D(&n1, &n2)
        } else {
            n1 += 1
            D(&n1, &n2)
        }
    }
    D(&i, &j)
    return ret
}

개선된 풀이
A 와 B배열을 sort 한 후 위에 말한 것 처럼 고친 풀이이다.
배열의 길이가 길어질 수록 컴파일 시간 차이가 급격하게 커질 것으로 보인다.

Two Pointer Algorithm