결정 알고리즘(이진탐색) - K번째 수

문제 (백준 1300)

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력 1

3
7

예제 출력 1

6

---

📝풀이과정

이차원 배열을 만들어서 flat으로 일차원 배열을 만든 후 오름차순 정렬을 하여 값을 구하면 당연히 메모리 초과가 나온다.

골드 1 문제가 이렇게 간단하게 풀리진 않을 것이다. O(N^2)을 수행하는 코드가 생기는 순간 테스트에 통과하지 못한다.

미리 유형이 나와있기에 이진 탐색을 활용해야한다는 것은 알고 있었지만 어떻게 사용해야할 지 애를 먹었다.

 

내가 탐색하고 싶은 대상은 배열을 오름차순으로 정렬했을 때 k번째에 위치한 값이다.

그렇다면 탐색 대상은 배열에 존재할 수 있는 모든 값의 범위에서 이진탐색을 진행할 것이다.

lt는 1이 될 것이고, rt는 n*n인 위의 예시에서 9가 된다. mid 값은 5이다.

5가 배열을 오름차순으로 정렬했을 때 k번째 위치한 값인지를 확인하면 된다. 주의할 점은 인덱스는 1부터 시작이다.

 

1	2	3
2	4	6
3	6	9

 

행을 보면 인덱스의 배수 리스트이다.

[ 1 2 3 ] 1의 배수

[ 2 4 6 ] 2의 배수

[ 3 6 9 ] 3의 배수

 

mid를 행의 인덱스로 나누어주면 각 행에 mid 값보다 같거나 작은 값의 갯수가 나온다.

5 / 1 ➡ 5인데 행의 길이는 n개이므로 n인 3으로 바꾼다.

5 / 2 ➡ 2

5 / 3 ➡ 1

따라서 mid보다 같거나 작은값의 갯수는 6이다.

나는 오름차순으로 정렬했을 때 7번째 요소를 찾고 싶다. 그렇다면 같거나 작은 값의 갯수를 늘려주어야한다.

늘려주기 위해서는 탐색 범위를 mid를 초과한 범위에서 찾아야한다. 즉, 6부터 rt까지의 범위에서 mid를 다시 찾아줘야한다는 것이다. 5보다 같거나 작은 값의 갯수가 6개인데 mid값을 5보다 작은 값으로 줄이게 된다면 범위를 만족하는 수의 갯수는 더 줄어들 게 될 것이다. 따라서 lt를 mid+1의 위치에 옮긴다.

 

lt = 6, rt = 9, mid = 7

 

이제 7을 가지고 위의 과정을 수행한다.

7 / 1 ➡ 3

7 / 2 ➡ 3

7 / 3 ➡ 2

 

7보다 같거나 작은 값의 갯수는 3+3+2인 8이다. 내가 찾고자 하는 7의 위치는 8의 범위안에 존재하게 된다.

이때는 반대로 rt의 범위를 줄여서 탐색한다.

 

lt = 6, rt = 6, mid = 6

 

6 / 1 ➡ 3

6 / 2 ➡ 3

6 / 3 ➡ 2

 

이번에도 8이 나오고 탐색이 종료되었다.

6보다 같거나 작은 값이 8개가 존재한다는 것이다. 내가 찾고 싶은 위치는 7이므로 8개의 숫자 중에 포함되어 있는 것이다.

따라서 정답은 6이 된다.

 

위의 과정이 이해가 되지 않을 수 있으니 예시로 조금 더 설명을 하면,

1 2 2 3 3 4 6 6 9

이렇게 오름차순으로 정렬이 되는데 7번째 요소는 6이다. 6보다 작거나 같은 숫자는 총 8개가 존재한다.

---

🛠코드

let [n, k] = require('fs').readFileSync(0).toString().trim().split('\n').map(Number);

function solution(n, k) {
  let lt = 1;
  let rt = n * n;
  let result = 0;
  while (lt <= rt) {
    let sum = 0;
    const mid = Math.floor((lt + rt) / 2);
    for (let i = 1; i <= n; i++) {
      if (Math.floor(mid / i) > n) sum += n;
      else sum += Math.floor(mid / i);
    }
    if (sum >= k) {
      result = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }

  return result;
}

console.log(solution(n, k));

---

느낀점

기존의 결정 알고리즘과 같은 유형이고, 접근 방법 또한 같지만 문제를 해결하는 과정은 몇 배나 더 어려움을 느꼈다.

탐색할 대상을 결정하는 것까지는 괜찮았지만 그 대상이 최적의 값인지 찾는 아이디어를 도출하는 것이 힘들었다.

더 다양한 문제를 많이 풀어야겠다.