[Kotlin] 백준 1920 : 수 찾기

문제 링크

1920번: 수 찾기

---

---

문제 해설

수열이 주어지고 이후 입력되는 숫자들을 주어진 수열에서 찾을 수 있는지를 검사하는 문제다. 일단 이 문제는 첫 입력으로 수열을 받은 후 단순히 in 키워드로 탐색을 하면 \(n\)과 \(m\)이 각각 최대 10만이므로 최악의 경우에 \(100,000\times 100,000=10,000,000,000\)번의 경우를 탐색하게 되어 시간초과가 발생한다.^[각주:1] 따라서, 좀 더 효율적인 탐색 방법을 찾아야 한다.

 

문제를 해결할 수 있는 방법은 이진 탐색을 이용하는 방법과 HashSet을 이용하는 방법이 있다. 이진 탐색을 이용하는 방법은 이진 탐색의 시간복잡도가 \(O(n\log n)\)이기 때문에 위의 방법에 비하면 압도적인 효율을 자랑한다. 이진 탐색은 Up&Down 게임과 비슷하게 어떤 수열과 찾고자 하는 수가 주어졌을 때, 해당 수를 찾을 때까지 수열을 반으로 나눠가면서 탐색하는 방법이다.

1부터 100까지의 수열 중 77을 이진 탐색으로 찾는 과정.

위 그림의 경우 1부터 100까지 존재하는 수열 중 77을 이진 탐색으로 찾는 과정을 나타낸 것이다. 이진 탐색은 현재 수열의 중간값을 찾고자하는 값과 비교하면서 수열을 계속 반으로 나누다가 마지막에 값을 찾게 된다.

 

주의해야할 점은 이진 탐색을 사용하기 위해서는 수열이 정렬된 상태여야 한다는 점이다.

---

HashSet을 이용한 방법은 중복을 갖지 않는 HashSet의 특성과 contains() 메소드의 시간복잡도가 \(O(1)\)이라는 점을 이용한 것이다. 따라서, 걸리는 시간 자체는 이 방법이 이진 탐색보다 약간 더 빠르다.

 

Collection 객체들의 시간복잡도에 대해서는 다음 링크를 참조하면 좋을 것 같다.

참조 링크 : [Java] 컬렉션들의 시간복잡도 (Collection Big-O)

---

이진 탐색 풀이

이진 탐색에 대한 이론적인 내용은 여기까지 하고, 이진 탐색으로 푸는 방법에 대해 알아보자. Kotlin의 배열은 배열을 정렬하는 sort() 메소드와 이진 탐색으로 해당 값의 인덱스를 찾아주는 binarySearch() 메소드를 제공한다. binarySearch() 메소드는 기본적으로 찾고자하는 값과 탐색을 시작할 인덱스, 탐색을 끝낼 인덱스를 파라미터로 받게 되는데 탐색을 시작할 인덱스와 탐색을 끝낼 인덱스를 생략하면 배열 전체에서 탐색을 하게 되고 해당 값이 존재하는 인덱스 값을 반환하게 된다. 만약 찾고자 하는 값이 배열에 존재하지 않는다면 음수값을 반환한다.

---

Code(이진 탐색)

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    var k = readLine().toInt()
    var st = StringTokenizer(readLine())
    val n = IntArray(k) { st.nextToken().toInt() }.sortedArray()
    k = readLine().toInt()
    st = StringTokenizer(readLine())
    repeat(k) {
        bw.write("${if (n.binarySearch(st.nextToken().toInt()) >= 0) 1 else 0}\n")
    }
    bw.close()
}

---

HashSet 풀이

HashSet을 이용한 방법은 더 간단하다. 입력된 수열의 값을 모두 HashSet에 삽입한 후, 찾고자 하는 값을 contains() 메소드로 탐색하면 된다.

---

Code(HashSet)

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    var k = readLine().toInt()
    var st = StringTokenizer(readLine())
    val set = HashSet<Int>()
    repeat(k) {
        set.add(st.nextToken().toInt())
    }
    k = readLine().toInt()
    st = StringTokenizer(readLine())
    repeat(k) {
        bw.write("${if (set.contains(st.nextToken().toInt())) 1 else 0}\n")
    }
    bw.close()
}

---

아래의 경우가 이진 탐색을 이용한 방법, 위의 경우가 HashSet을 이용한 방법이다. HashSet을 이용한 방법이 약 11% 정도 더 빠르다는 것을 알 수 있다.

1. 일반적으로 컴퓨터는 1초에 1억회의 연산을 수행할 수 있다고 가정하므로, 100억번의 경우 100초나 걸리게 된다. [본문으로]