문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

첫 번째 풀이: contains 사용

import Foundation

let N = readLine()!
let A = readLine()!.components(separatedBy: " ").map { Int($0)! }
let M = readLine()!
let B = readLine()!.components(separatedBy: " ").map { Int($0)! }

B.map { A.contains($0) ? print("1") : print("0") }

시간초과 떴다... 탐색 문제인데 오만하게 contains로 찾으려 했던 걸 반성합니다. O(N*M)인데 말이에요....

두 번째 풀이: 이진 탐색

일단 탐색 알고리즘 하면 가장 먼저 생각나는 게 이진 탐색.
1. 찾고자 하는 대상 배열을 먼저 오름차순으로 정렬한 뒤,
2. 중간값을 찾아서 작으면 왼쪽 배열, 크면 오른쪽 배열 선택
3. 반복하며 범위 좁히기

정렬은 간단하게 시간 복잡도가 O(NlogN)인 sort() 쓰면 될 것 같다.

이진 탐색 함수 binarySearch()도 어렵지 않게 구현 가능하다.

func binarySearch(_ array: [Int], _ target: Int) -> Bool {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        
        if array[mid] == target {
            return true
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return false
}

left, right 각각 양 끝에서부터 시작해서 mid index를 구하고, array[mid] 판별 후 target과 일치할 경우 true를 리턴한다. 작을 경우 left의 포인터를 mid + 1로 옮긴다. 클 경우 right의 포인터를 mid - 1로 옮긴다.
계속 반복하다가 left의 값이 right의 값보다 크거나 같으면 종료(= 찾는 값이 없음)

let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map { Int($0)! }
let M = Int(readLine()!)!
let B = readLine()!.split(separator: " ").map { Int($0)! }

A.sort()

for num in B {
	print(binarySearch(A, num) ? 1 : 0)
}

세 번째 방법: Set 사용

다른 방법이 또 있나 고민하던 중 배열과 비슷한 Set을 사용하는 방법을 찾았다. 순서가 따로 있는 게 아닌 해시 테이블이기 때문에 값을 찾을 때 시간 복잡도가 O(1)이 걸린다.

let N = Int(readLine()!)!
let A = Set(readLine()!.split(separator: " ").map { Int($0)! })
let M = Int(readLine()!)!
let B = readLine()!.split(separator: " ").map { Int($0)! }

for num in B {
    print(A.contains(num) ? 1 : 0)
}

실행 시간이 Set이 더 빠를 거라고 생각했는데 오히려 이진 탐색이 더 빠르다. 아마 입력 받은 배열을 Set으로 변환하는 과정이 추가돼서 그런 듯하다. 순수하게 탐색 시간만 비교하면 Set 쪽이 빠르긴 하다.

입력 받는 게 너무 번거롭다... 프로그래머스는 함수 제출 형식이라 편했는데(ㅠㅠ)