[s2 - 8주차 - 4] K번째 수

[soheeGit]

문제

• 문제 사이트: 백준
• 문제 이름: K번째 수
• 문제 번호: 1300

문제 풀이 템플릿

### 시간복잡도 생각해보기
- 

### 풀이 아이디어
- 

### 의사코드 / 풀이 과정
- 

[soheeGit]

시간복잡도 생각해보기

• O(N log N)

풀이 아이디어

• mid보다 작거나 같은 숫자가 몇 개 있는지가 핵심이다!

의사코드 / 풀이 과정

• solve

static long solve() {
    long left = 1, right = k;
    long answer = 0;

    while(left <= right) {
        long mid = (left + right) / 2;
        long count = 0;

        for(int i=1; i<=N; i++) {
            count += Math.min(N, mid / i);
        }

        if (count >= k) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return answer;
}