[Silver IV] Sort 마스터 배지훈의 후계자 - 20551

문제 링크

성능 요약

메모리: 90808 KB, 시간: 3120 ms

분류

이분 탐색(binary_search), 자료 구조(data_structures), 정렬(sorting), 트리를 사용한 집합과 맵(tree_set)

문제 설명

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 NN개의 원소를 가진 배열AA를 주고, AA의 원소들이 오름차순으로 정렬된 배열BB를 만들게 한다. 그다음 MM개의 질문을 한다. 각 질문에는 정수 DD가 주어진다. 제자들은 주어진 정수DD가 BB에서 가장 먼저 등장한 위치를 출력하면 된다. 단, DD가 BB에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

입력

첫째 줄에 배열AA의 원소의 개수 NN과 질문의 개수 MM이 공백으로 구분되어 주어진다.

다음 줄부터 NN줄에 걸쳐 정수 A0,A1,...,AN−1A0,A1,...,AN−1이 주어진다.

다음 줄부터 MM줄에 걸쳐 정수 DD가 주어진다.

출력

MM개의 질문에 대해서 주어진 DD가 BB에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1를 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)

---

풀이

• 여느 이분 탐색과 같은 방식이 풀이이지만 출력 조건을 보면 ‘처음으로 등장한 위치’를 찾으라고 나온다. 즉, 비교 당하는 배열에 중복된 숫자가 있을 거라는 무시무시한 이야기다.
• 기본 이분 탐색 구조는 첫 조건문에서 찾으려는 숫자가 mid 인덱스 값이 맞으면 while을 리턴으로 끝냈지만
  우리는 계속 찾아야한다. 또한 처음 나오는 위치를 찾아야 한다.
• 그래서 먼저 나온 mid를 다른 변수에 저장해두고 범위를 왼쪽으로 좁혀나간다. 그렇게 끝까지 가다보면 while은 끝나게 되고 내가 마지막에 mid를 저장해둔 변수를 반환하면 된다.
• 숫자를 찾지만 가장 먼저의 인덱스를 찾는다는게 이 문제의 특징이다.

답

fun main() {

    val (N, M) = readln().split(" ").map { it.toInt() }
    val arr1 = mutableListOf<Int>()
    val arr2 = mutableListOf<Int>()
    repeat(N) { arr1.add(readln().toInt()) }
    repeat(M) { arr2.add(readln().toInt()) }
    arr1.sort()
    arr2.forEach { println(cal(arr1, it)) }
}
fun cal(arr1:List<Int>, findNum:Int) : Int {
    var first = 0
    var last = arr1.size-1
    var mid : Int = -1
    var cnt = -1
    while(first <= last) {
        mid = ( first+last ) / 2
        if(findNum==arr1[mid]) {
            cnt = mid
            last = mid -1
        }
        else if(findNum < arr1[mid]) {
            last = mid-1
        }
        else {
             first = mid+1
        }
    }
    return cnt
}