[알고리즘풀기] 백준 10815번 숫자카드

문제:
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력:
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

문제분석하기 

이중 For문으로 풀 수는 있지만 그렇게 풀었다가는 시간복잡도가 O(n2) 으로 시간초과로 통과하지 못할 것이다. 

그래서 O(logN) 으로 풀기 위해 이분탐색을 사용해 보았다. 

 

이분탐색이란 : 

1.정렬된 배열의 2.중간값과 3.검색하고자하는 값 이 중요하다고 볼 수 있다. 

검색하고자하는 값이 정렬된 배열의 중간값기준으로 큰지 작은지를 비교한후에 해당 범위를 반으로 줄여가며 그 값을 찾는 탐색알고리즘이 이분탐색이다.

 

아래의 gif로 잘 표시해둔 블로그가 있어 첨부합니다.

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

이제 중요한 것은 이해한 알고리즘을 코드로 정착화시키는것! 

차근차근 시도해보자. 

 

    var leftIndex = 0 //mid 
    var rightIndex = sangunCards!.count-1
    var hasSameValue = false
    
    //핵심코드 
    while leftIndex <= rightIndex { 
        //중간인덱스를 구해준다
        let midIndex = (leftIndex + rightIndex)/2

        if mElement > sangunCards![midIndex] {
        //찾고자 하는 값 mElement가 정렬된 배열 sangunCards의 중간인덱스의 값보다 크면 
        //leftIndex의 값을 midIndex에서 1을 더해줌으로서 정렬된 배열의 midIndex 이전값 탐색의 시간을 절약
            leftIndex = midIndex + 1
        }else if mElement == sangunCards![midIndex] {
        //값이 같을 경우를 판단하기위한 hasSameValue 변수의 값을 true로 변경
        // 이부분은 각 자 구현하기 나름!
            hasSameValue = true
            //동일한 값이 나온경우 더 탐색할 필요가 없다고 생각하여 break 
            break
        }else{
        //반대일 경우에는 midIndex 값에서 1을 빼줌으로서 정렬된 배열의 midIndex 이후의 값을 탐색하는 시간을 절약
            rightIndex = midIndex-1
        }
    }

 

 

 

코드 전체 내용

 

let sangun = Int(readLine()!)!
let sangunCards = readLine()?.split(separator: " ").compactMap{Int($0)}.sorted()
let m = Int(readLine()!)!
let mIntegers = readLine()?.split(separator: " ").compactMap{Int($0)}

var soulutionArrray = [Int]()
mIntegers?.forEach({ mElement in
    var leftIndex = 0
    var rightIndex = sangunCards!.count-1
    var hasSameValue = false

    while leftIndex <= rightIndex {
        let midIndex = (leftIndex + rightIndex)/2
        if mElement > sangunCards![midIndex] {
            leftIndex = midIndex + 1
        }else if mElement == sangunCards![midIndex] {
            hasSameValue = true
            break
        }else{
            rightIndex = midIndex-1
        }
    }
    
    //way1
    //hasSameValue 값에 따라서 1 or 0 을 append 시켰다. 
    soulutionArrray.append(hasSameValue ? 1 : 0)
})

// 출력조건이 문자열이라 array를 string으로 변화하여 출력
print(soulutionArrray.map{String($0)}.joined(separator: " "))

 

비하인드 스토리 

 

문제 풀고 테스트 코드 제출했는데 틀렸습니다! 떠서 

혹시나 삼항연산자를 써서 컴파일 속도에 영향을 미쳤나..싶어서 

if 문으로 변경해서 해봤는데 또 틀렸다라고 떴다... 알고보니 출력문을 array 자체로 출력을 하고 있었던...😱 

문제를 꼼꼼하게 항상 읽도록 노력하자!

if hasSameValue {
    soulutionArrray.append(1)
}else{
    soulutionArrray.append(0)
}

 

둘 다 사용해도 통과된다는걸 확인!

 

 

 

 

참고자료 :

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

Binary Vs Linear Search Through Animated Gifs

 

https://medium.com/@RobertGummesson/regarding-swift-build-time-optimizations-fc92cdd91e31#.hx5f9wsty

Regarding Swift build time optimizations

https://medium.com/marojuns-ios/swift-%EC%BB%B4%ED%8C%8C%EC%9D%BC-%EC%86%8D%EB%8F%84%EB%A5%BC-%ED%96%A5%EC%83%81%EC%8B%9C%ED%82%A4%EC%9E%90-51617509e35

Swift 컴파일 속도를 향상시키자