Swift) 백준 1920번: 수 찾기

iOS공부 전의 개발 공부를 돌아보면 다 겉핥기 식으로 한 것 같다

이유는 단순했던 것 같다. 하기 싫어서. 

개발 공부를 좋아서 시작한 건 절대 아니다 오히려 싫어하는 쪽에 가까웠지만 좋아하는 걸 찾기가 너무 힘들자 차라리 극도로 혐오하지 않는 것을 진로로 삼자 해서 막연히 시작했었다.

이리저리 여러 분야 왔다 갔다 하면서 지식은 휘발성이 되어 다 사라졌지만 그 기간이 아니었다면 iOS 개발을 시작 못했을 것 같다.

현재는 iOS 개발이 너무 재밌고 더 잘하고 싶다. 앱을 만드는 게 재밌고 더 효율적인 코드 짜고 싶다.

어쨌든 방황한 기간 동안 알고리즘 공부를 했던 적이 있다. 역시나 하고 싶어서 했던 건 아니고 해야만 할 것 같아서 하다가 또 얼마 안 가서 그만두었던 기억이 있다..

 

하지만 근래에 iOS 개발 공부와는 별개로 Swift라는 언어와 내가 친한가? 많이 스스로 질문을 했었다.

그래서 백준에 가서 쉬운 문제를 그럼 풀어보자! 해서 문제 풀이를 시도했는데, 생각보다 상태가 심각한 걸 깨달았다.

문법을 제대로 모르니 머릿속에 방법은 떠올라도 작성을 할 수 가없었다.

그래서 문제 푸는 시간도 갖는 게 맞는 거 같아 새로운 카테고리를 만들었다.

 

https://www.acmicpc.net/workbook/view/2418

문제집: BOJ 길라잡이 베타 (1) (ryute)

BOJ 길라잡이를 첫 문제부터 하나씩 풀어볼 예정이고 오늘은 첫문제 수 찾기이다.

 

우선 현재 내 머릿속에 지식으로써 자리 잡은 알고리즘은 단호하게 없다고 말할 수 있다. 

그래서 일단 처음엔 검색하기 전에 하드코딩이라도 해봤다.

 

 

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

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

for num in 0..<mArray.count {
    
    if nArray.contains(mArray[num]) {
        print(1)
    } else {
        print(0)
    }
}

결과는 시간 초과다.

그럴 법도 한 게 서버 측에서 어떠한 데이터를 보낼지 모르는데 for문을 통해 하나씩 비교하는 건 문제에서 요구한 시간 안에 할 수 없기 때문이다.

하지만 이 코드를 짜는데도 애를 먹었다. 현재까지 진행한 프로젝트에서는 split이나 readLine 등을 쓸 필요가 없었기 때문이다.

다시 한번 언어 학습의 중요성을 깨달았다.

 

더 효율적인 코드를 통해 알고리즘을 공부하여 적용시키기로 했다.

백준 문제에는 쓰이는 알고리즘이 어떤 것이 있는지 알려준다.

이진 탐색(이분탐색)을 사용하기로 결정했다. 

 

이진탐색 (Binary Search)

---

이진 탐색은 데이터가 정렬되어있는 어떤 배열에서 특정한 값을 찾기 위한 알고리즘이다.

배열의 중간에 있는 랜덤의 값을 선택하여 찾고자 하는 값(a)과 비교한다. a가 중간 값보다 작으면 중간 값을 기준으로 왼쪽에 있는 데이터들을 대상으로 탐색을 하고, a가 중간 값보다 크면 배열의 오른쪽을 대상으로 탐색을 한다.

해당 값을 찾을 때까지 이 과정을 반복하는데, 이렇게 생각만 해도 하나씩 일일이 탐색을 하는 것보다는 더 효율적이라는 걸 알 수 있다.

 

 

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

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

nArray.sort()

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

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

이진 탐색을 적용하여 작성한 코드고 결과는 정답이었다.

탐색을 할 배열은 정렬을 해줘야 하는 걸 잊지 말자. 정렬이 안되어있으면 의미가 없는 알고리즘이다.

 

 

 

 

 

 

---

문제를 다 풀고 찾은 다른 방법도 공유해볼까 한다.

https://velog.io/@yc1303/%EB% B0% B1% EC% A4%80-Python-Swift-1920% EB% B2%88-%EC%88%98-%EC% B0% BE% EA% B8% B0

let n = readLine()!
let setA = Set(readLine()!.split(separator: " "))
let m = readLine()!
let setM = readLine()!.split(separator: " ")

for i in setM {
    if setA.contains(i) {
        print(1)
    } else {
        print(0)
    }
}

cobugi님의 코드인데, 이 문제에서는 단순히 데이터가 배열에 있는지 없는지 여부를 판단하는 문제로 중복이 허용되지 않는 set을 사용하면 된다고 작성하셨다.

실제로 백준에서도 정답이라고 나온다. 코드가 되게 짧고 간결한데 이런 방법도 있구나 하고 보면 좋겠다.