[Swift]BOJ-1920

BOJ - 1920번, 수 찾기 

문제 📑

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

문제 정리 ▾ 

BOJ - 1290

• 첫 번째 Array가 두 번째 Array의 원소를 가지고 있는지를 판별하여, 포함되어 있으면 "1"을 출력하고, 포함되어 있지 않으면 "0"을 출력한다.

 

접근 🚶🏻

첫번째 방법 ▾

• 문제를 보자마자 contains가 생각이 났다.

contains는 문자열 혹은 배열에서 특정 문자가 포함되어 있는지를 Boolean값으로 리턴해주는 함수이다.

• 아래와 같이 풀어보았다.

import Foundation

let n = Int(readLine()!)!
let nNumbers = readLine()!.split(separator: " ").map{ Int($0)! }
let m = Int(readLine()!)!
let mNumbers = readLine()!.split(separator: " ").map{ Int($0)! }

mNumbers.forEach {
    nNumbers.contains($0) ? print("1") : print("0")
}

• 위와 같이 제출을 했으나 시간 초과가 나왔다.
• print()가 시간 초과에도 어느 정도 영향이 있다고 생각은 했으나, 출제자의 의도는 출력에 관한 의도가 아닐 것 같아서, 직접 알고리즘을 이용해 구현해보았다.

 

두 번째 방법 ▾

• 이진 탐색을 이용해보았다.

import Foundation
let n = Int(readLine()!)!
var haveLst = readLine()!.split(separator: " ").map{Int($0)!}.sorted(by: <)

let m = Int(readLine()!)!
var standardLst = readLine()!.split(separator: " ").map{Int($0)!}

func binarySearch(_ arr: [Int], _ target: Int) -> Int{
    var start = 0
    var end = arr.count - 1

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

for i in 0..<m {
    print(binarySearch(haveLst, standardLst[i]))
}

• 이진 탐색을 이용해 문제를 풀 수 있었다.
• 이진 탐색에 대해서는 아래에 따로 정리해보았다.

 

Additional 📂

• 정말 오랜만에 알고리즘을 다시 시작해서 기본 문법도 생각이 안 날 때가 있었다.
• 한창 알고리즘을 공부할 때 숏코딩에 집착했던 나는 이번 이진 탐색에서도 아주 조금 엿볼 수 있었다.
• 개발을 하는데 있어서 알고리즘을 굳이 공부해야 되냐는 질문도 있었지만, 좀 더 창의적인 발상을 얻고자 하게 된다는 답을 했다.
• 정말 많이 부족하다는 것을 매일 느끼지만, 더 열심히 노력해서 덜 부족한 iOS 개발자가 되어보려고 한다. 😆

---

이진 탐색은 무엇인가 ❓

정의 ▾

• 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
• 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.
• X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
• 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.