백준 1300번 K번째 수 - SWIFT

문제

---

세준이는 크기가 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]를 출력한다.

 

문제 링크

1300번: K번째 수

 

 

풀이

---

솔직히 규칙을 찾는게 정말 어려웠다.

단순 이분탐색이라길래 어떤 부분을 이분탐색해야할까를 고민했는데 결국에는 그 해답을 스스로 구하지 못하고 접근법을 검색했다.

 

접근법

먼저 문제에서 제시한 배열을 살펴보자.

문제에서 제시한 배열은 아래와 같은 규칙으로 구성되어있다.▼

 

 

우리가 구하려는 것은 이 배열을 1차원 배열로, 순서대로 배열했을 때 K번째 수가 무엇인지이다.

그렇다면 말을 다시 바꿔 생각해보면, K번째 수 아래에는 K - 1개의 수가 있다는 것이다.

즉, 우리는 이 배열에서 특정 수를 대입했을 때 그 수보다 작은 K - 1개의 수가 배열에 있음을 확인하면 되는 것이다.

그걸 확인할 때, 이 배열이 배수로 이루어져있음으로 이용하는 것이다.

이 배열에서 5보다 작은 수가 몇 개 있는지를 세보겠다.

지금은 이렇게 하나씩 세어줬지만, 그럴 필요가 없다.▼

 

 

5를 y축 인덱스로 나누면 된다.

하지만 1번 인덱스 처럼 수가 초과해서 나올 수 있다.▼

 

 

특정 행에서 특정 수보다 작은 수의 최대값은 언제나 N개이므로, N보다 큰 값이 나오면 N으로 바꿔 대입해주면 된다.▼

 

 

이렇게 하면 개수를 간단한 계산으로 셀 수 있다.

 

 

프로그램 동작

---

그러면 위의 접근법과 이분탐색을 이용해보겠다.

우리는 정답 값을 이분탐색해 볼 것이다.

그러면 정답 값의 범위를 알아야 하는데, 정답 값의 범위는 1과 K사이의 수가 된다.

어차피 K번째 아래의 인덱스에 들어있는 값들은 전부 K보다 작기 때문이다.

그러므로 왼쪽 값은 1로, 오른쪽 값은 K로 초기화해주고 이분 탐색을 시작한다.

예제에 나와있는 값인 N = 3, K = 7로 예시를 들어보겠다.

 

1. 왼쪽 값: 1, 오른쪽 값: 7 로 세팅을 해놓고 왼쪽과 오른쪽의 중간 값보다 작은 수가 몇개 있는 지 세어본다.

6개로 K값보다 작다.▼

 

 

2. K값보다 적게 나왔으므로, 4 이하의 값은 정답에 해당되지 않는다.

따라서 왼쪽 값을 중간 값 + 1로 바꿔준다.

중간 값도 갱신해준다.▼

 

 

3. 갱신된 중간 값으로 다시 1번 과정을 수행한다.

이번엔 값이 더 크게 나왔다.▼

 

 

4. 값이 딱 맞지 않아도 괜찮다.

중복 값이 있어서 제시된 K값보다 크기만 하면 된다.

수가 더 많이 나왔으므로, 정답 값으로 갱신해주고 오른쪽 값을 중간 값 - 1로 바꿔준다.

중간 값도 갱신해준다.▼

 

 

5. 왼쪽과 오른쪽 값이 같으므로 이번 과정에서 끝이 난다.

1번과 똑같이 수행해준다.

값이 더 크지 않으므로 정답 값의 갱신은 이루어지지 않고, 왼쪽 값이 6이 되면서 종료된다.▼

 

 

6. 아까 3, 4번에서 갱신됐던 값 6이 정답이 된다.

 

 

Swift 코드

---

let N = Int(readLine()!)!
let K = Int(readLine()!)!
var left = 1
var right = K
var answer = 0

while left <= right {
    let mid = (left + right) / 2
    var sum = 0

    for i in 1...N {
        sum += min(mid / i, N)
    }
    if sum >= K {
        answer = mid
        right = mid - 1
    } else {
        left = mid + 1
    }
}
print(answer)