백준 1920번 수 찾기 - SWIFT

문제

---

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

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

문제 링크

1920번: 수 찾기

 

 

풀이

---

배열 안에 특정 원소가 있는 지 확인하는 가장 쉬운 방법은 앞에서 부터 하나씩 비교하기다.

하지만 이 문제에서 그 방법을 사용하게 되면, 100,000 * 100,000 번 연산을 하게 된다.

더 효율적으로 원소를 탐색하는 방법을 찾는 문제다.

문제에서는 이분 탐색을 쓰라고 힌트에 이분 탐색을 써놨다.

그러나 Swift에서는 다른 방법의 풀이가 존재한다.

하지만 일단은 문제의 목적은 이분 탐색이므로 이분 탐색으로 푸는 법 부터 보고 Swift에서 가능한 풀이를 보겠다.

 

이분 탐색

이분 탐색은 이름 그대로 두 부분으로 나누어서 탐색하는 방법을 말한다.

기본적으로 이분 탐색을 사용하려면 배열이 정렬되어있어야 한다.

 

1. 먼저 무작위로 들어온 수를 정렬해준다.

그리고 양 끝 인덱스와 중앙의 인덱스를 구한다.

start, end. mid가 각각의 인덱스를 뜻한다.▼

 

 

2. mid에 해당하는 값과 찾으려는 값을 비교해본다.

만약 찾는 값이 더 크다면, start 값을 mid 다음 값으로 바꿔준다.

반대로 찾는 값이 더 작다면, end 값을 mid 이전 값으로 바꿔준다.

그리고 mid 값을 다시 계산해준다.▼

 

 

3. 만약 mid 값이 찾는 값과 동일하다면, mid 값을 반환하고 함수를 끝낸다.

하지만 mid값이 찾는 값과 여전히 동일하지 않다면, 앞의 과정을 반복해준다.

 

4. start가 end값 보다 크거나 같아지게 되는 순간 종료한다.

이렇게 될 때 까지 일치하는 값을 찾지 못했다면, 해당 수는 배열에 존재하지 않는 것이다.

이분 탐색을 통해서 값을 찾게 되면, 일반 순회보다 연산횟수가 현저히 줄어 더 빠르게 값을 탐색할 수 있다.

 

 

Swift에서의 풀이

사실 이 방법은 Swift에서'만' 풀 수 있다고 하기는 힘들다.

Set 자료형이 Swift와 같은 방식으로 구현되어있다면, 사용 가능한 풀이다.

일단 Set의 대표적인 특징을 보자면 아래와 같다.

 

1. 같은 데이터가 중복해서 있을 수 없다.
2. 순서의 개념이 딱히 없다.
3. 원소에 바로 접근할 수 있다. O(1)

우리는 이 특성 중 세번째 특성을 이용할 것이다.

1. 일단 들어오는 값들을 Set에 전부 넣어준다.
2. Set에서는 값을 탐색할 때 시간 복잡도가 O(1)이므로, 바로바로 확인해준다.

 

이게 전부다.

 

심지어 이 방법이 앞서 푼 이분 탐색보다 더 빠르다...(약 8ms 정도 더 빠르다.)

어떤 방법으로 풀 지는 개인이 느끼기에 더 쉬운 방법으로 하면 된다.

풀이는 이분 탐색 풀이로 올려놓았다.

Set을 이용한 풀이는 구현이 굉장히 쉽다.

 

 

Swift 코드

---

import Foundation

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() }

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

var file = FileIO()
let N = file.readInt()
var A = Array(repeating: 0, count: N)
for i in 0..<N {
    A[i] = file.readInt()
}
let M = file.readInt()
var X = Array(repeating: 0, count: M)
for i in 0..<M {
    X[i] = file.readInt()
}
var answer = ""

A.sort()

func binarySearch(_ target: Int) -> Bool {
    var start = 0
    var end = A.count - 1
    var mid = (end + start) / 2

    while (end - start) >= 0 {
        if A[mid] == target {
            return true
        } else if A[mid] <= target {
            start = mid + 1
        } else {
            end = mid - 1
        }
        mid = (end + start) / 2
    }
    return false
}

for i in X {
    if binarySearch(i) {
        answer += "1\n"
    } else {
        answer += "0\n"
    }
}
print(answer)