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


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

profile
iOS 개발, Flutter 개발, Swift, Dart, 42 Seoul 3기

0개의 댓글

Powered by GraphCDN, the GraphQL CDN