(JAVA) 백준 1300번 : K번째 수

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

1300번: K번째 수

 

이분 탐색 문제인데

 

정답률에 비해 난이도는 높았었던 문제.

 

진짜 생각이 안나서 해설을 참고했었다.

 

 

 

 

핵심은 이거다.

 

 

 

  -  정렬된 배열 : K번째에 해당할 것 같은 수 (행렬 내 범위. 1 ~ K)

  ***  최댓값을 n * n 이 아닌 K로 잡는 이유는 K번 째에 해당하는 수는 절대 K를 초과하지 않기 때문에 탐색 시 시간 절약을 위해서다. 

  ***  K를 초과하지 않는 이유는 중복된 값이 두 개씩은 존재하기 때문에 B행렬(1차원 행렬) 로 바꿔도 K를 넘지 않는다.

 

 

  -  계산 방법 : 이분탐색 진행.

      ->  mid값을 얻고, 1 ~ n 까지 For문을 탐색하며 해당 mid와 같거나 작은 수들을 count 한다.

      ->  이 때, count += Math.min(n , mid / i) 를 통해 count할 수 있다.

 

        

  -  mid / i ?

    ->  i 는 1 ~ n 행 중 i번째 행을 가리킨다. 

    ->  2차원 배열 A에서 i 번째 행의 원소들 중 mid 값보다 같거나 작은 원소의 개수

 

 

  -  count 시 n과 mid / i 중 최솟값을 선택하는 이유는?

    -> mid / i 는 절대 n보다 클 수 없기 때문에. (행렬 상 i행의 원소 개수는 무조건 n개이다.)

    -> 그렇기 떄문에, mid / i 값이 n보다 크게 나온다면 그냥 n을 count 하면 된다.

 

 

예시를 들어보자.

 

N = 4 인 배열 모습

 

N = 4에서 만약 mid 값이 7이라면, count는 어떻게 될까?

 

  i = 1 -> 1, 2, 3, 4  //  7 / 1 = 7 > 4 라서, n = 4개

  i = 2 -> 2, 4, 6  //  7 / 2 = 3, 3개

  i = 3 -> 3, 6  //  7 / 3 = 2, 2개

  i = 4 -> 4  // 7 / 4 = 1, 1개

  

총 4 + 3 + 2 + 1 = 10개

따라서, 7은 최대 10번째에 해당한다. (하지만 7은 행렬 내 존재하지 않기 때문에 PASS.)

마찬가지로, 6은 최대 10번째에 해당한다.

 

 

 

우선, 행렬의 원소는 i의 배수에 해당한다.

 

그렇기 때문에 count를 할 때 위 예시처럼 각 행 별로 mid / i 를 수행하면 된다.

 

 

 

  -  그래서 나온 결과 count와 k를 비교한다.

    ->  count >= k 인 경우, mid는 k번째 수에 포함된다. 그리고 숫자를 낮춰서 재탐색한다. (high = mid - 1)

    ->  count < k 인 경우, mid는 k번째 수에 절대 포함되지 않는다. 그래서 개수를 늘리기 위해 숫자를 높여서 재탐색한다. (low = mid + 1)

 

 

 

 

 

 

위 핵심이 곧 매커니즘이기 때문에 별도 매커니즘을 작성하지 않겠습니다.

 

소스코드를 참고해주시고, 궁금한 사항이 있으시면 댓글 부탁드립니다.

 

감사합니다!

 

소스코드

---