Swift) 백준 10815번: 숫자 카드

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

10815번: 숫자 카드

 

드디어 알고리즘이 왜 필요한지, 어떤 알고리즘을 써야 할지 나 혼자 생각하며 문제를 풀었다!

쉬운 문제라 다른 사람에게는 당연할지몰라도 오늘은 문제를 혼자 해결하며 정말 기분이 좋았다.

처음부터 문제를 맞힌건 아니고 다른 날과 같은 고난의 시간을 겪었다.

 

 

 

최초 제출: 시간초과

---

import Foundation

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

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

var result = ""

for k in 0..<m {
    if nCard.contains(mCard[k]) {
        result += "1 "
    } else {
        result += "0 "
    }
}

print(result)

처음엔 readLine()을 통해 숫자 카드를 입력받고, 비교를 할 카드 배열을 이진 탐색을 위해 오름차순으로 정렬을 하였다.

그 후 상근이의 카드 안에 입력한 카드가 포함되어있는지 contains를 이용해 탐색을 하였는데, 이것이 시간 초과의 주원인이 되었다.

contains는 요소를 하나하나씩 돌며 포함 여부를 판단하는데, 최대 50만 개의 카드를 입력받는 문제에서는 상당히 많은 시간을 요구하게 된다.

시간 초과의 원인을 처음부터 바로 알았던 건 아니어서 여러 형태로 많은 시도를 하였다.

그러다가 모든 배열을 탐색할 필요가 없다고 생각했고 그때 생각난 게 이진 탐색 알고리즘이었다.

첫날 문제(1920)를 풀 때만 하더라도 이진 탐색이 뭔지 왜 필요한지 잘 모르는 상태로 공부하고 응용했는데, 어떤 알고리즘을 써야 하는지 단계별로 생각하며 접근하였다.

 

또한 머리로만 생각하는 것이 아니라 필기나 그림을 그리며 문제를 해결할 방법을 찾았는데, 혹시 문제 해결에 어려움을 갖고 있는 사람이 있으면 이 방법을 꼭 추천해주고 싶다.

이러한 과정을 통해 이진 탐색을 통해 시간을 단축할 수 있겠구나! 생각했다.

 

 

 

 

 

최종 정답

---

import Foundation

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

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

var result = ""

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

    while start <= end {
        let mid = (start + end) / 2

        if nCard[mid] == target {
            result += "1 "
            return
        } else if nCard[mid] < target {
            start = mid + 1
        } else if nCard[mid] > target {
            end = mid - 1
        }
    }
    result += "0 "
}

for k in 0..<m {
    binarySearch(nCard, mCard[k])
}

print(result)

이진탐색을 통해 문제를 해결하였다.

mid를 통해 target에 한 단계씩 접근하면서 mid == target이 될 때 result에 “1”을 추가해주며,

동일한 원소를 찾지 못할 때 (start ≤ end) result에 “0”을 추가해준다.

처음엔 start와 end를 mid와 target의 관계를 통해 다시 설정할 때 왜 mid+1이나 mid-1을 하는지 몰랐다.

그 이유는 mid 자체가 target에 접근하는 용도로 쓰이기 때문에 이진 탐색의 중간지점(mid)이 target보다 작을 때는 새로운 시작 지점을 정하는데 1을 더해줌으로써 if문의 nCard [mid] == target을 거쳐 존재 여부를 파악하게 해 준다. 만약 mid가 target이 아닐 시는 이를 반복함으로써 target에 한 단계 한단계 다가가는 것이다.

end에 대해서는 반대로 생각하면 되겠다.

 

느리지만 이런 식으로 한 단계 한단계 알고리즘에 대한 이해와 응용 능력을 키우는 게 목표이다.

처음 이진 탐색 관련 문제를 풀 때는 도저히 시간도 없고 문제도 안 풀릴 때 알고리즘 관련 글을 찾아보며 응용을 했는데, 그러면서 기분이 좋지 않았다. 

"이렇게 한다고 내가 이 알고리즘을 습득하는 건가?" 

하지만 오늘처럼 전에 배웠던 게 생각이 난 게 이런 과정이 있어서라고 생각한다.

누구나 처음엔 어려운 시기를 거쳐 문제 해결 능력을 키운다고 생각하기 때문에 앞으로 다가올 문제에 대해서 스트레스를 받는 것보다 배우는 과정이라 생각하기로 했다.

 

 

 

---

 

 

중간에 약속이 있어서 나갔다 왔는데 밖에서 해결방법을 생각해 집에 와서 바로 적용했더니 한 번에 맞았다!!