[백준 1300][파이썬] K번째 수

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

1300번: K번째 수

이진 탐색으로 해결할 수 있다.

 

1. 배열의 가장 작은 값(low)과 가장 큰 값(high)의 중간 값(mid)부터 탐색을 시작한다.

 

2. 해당 값보다 작은 값의 개수와 같은 값의 개수를 구한다.

 

3. k가 mid 값보다 작은 값의 개수와 해당 값과 같은 값의 개수 사이에 존재한다면 mid를 출력하고 끝낸다.

 

4. k가 mid 값보다 작은 값의 개수보다 작거나 같다면 low 부터 mid-1 까지 다시 조사한다.

 

5. k가 mid 값보다 작거나 같 값의 개수보다 크다면 mid+1 부터 high 까지 다시 조사한다.

 

알고리즘 자체는 어렵지 않으나 2번에 해당하는 개수를 구하는 부분에서 시간을 줄여야 이 문제를 해결할 수 있다.

 

배열의 형태를 잘 보면 시간을 단축할 수 있다.

6을 기준으로 보자.

아래 행으로 갈 수록 6은 왼쪽으로 가는 모습을 확인할 수 있다.

 

각 행은 오름차순으로 이루어져 있고 아래 행으로 갈수록 같은 열의 값은 커지기 때문이다.

 

그래서 마지막 인덱스부터 시작하여 각 행마다 처음으로 6보다 작거나 같은 수가 나오는 행의 인덱스를 업데이트 한다.

 

물론 각 행이 끝날 때마다 해당 인덱스+1을 cnt에 더해주고 만약 6과 같은 것이 있다면 same_cnt에 1을 더해준다.

 

그리고 인덱스가 0보다 작아진다면 아래 행에서 더이상 6보다 작은 값이 존재하지 않으므로 이를 끝낸다.

 

반복문이 모두 끝났을 때는 6보다 작은 값과 6과 같은 값의 개수를 알고 있으므로 이와 k를 비교하면 된다.

 

처음에는 2차원 배열을 직접 만들어서 해당 인덱스의 값을 비교하는 방식을 사용했는데 메모리 초과가 발생했다.

 

그런데 문제의 조건을 잘 보면 행과 열의 인덱스만 알고 있어도 해당 값을 구할 수 있다.

 

즉 이차원 배열을 직접 만들 필요가 없는 것이다.

 

    for i in range(1, n+1):
        while i*idx>x and idx>=1: #처음으로 x보다 같거나 작아지는 인덱스를 구하기 위함
            idx-=1
        if i*idx==x: #반복문이 끝났을 때 x와 같다면 same_cnt 증가
            same_cnt+=1
        elif idx<1: #idx가 1보다 작으으면 조사할 필요가 없음음
            break
        cnt+=idx #x보다 작은 것의 개수

 

<전체 코드>

import sys
iinput=sys.stdin.readline
def x_is_greater(low, high):
    x=(low+high)//2
    cnt=0 #x보다 작은 것의 개수 
    same_cnt=0 #x와 동일한 것의 개수
    idx=n #큰 것부터 시작해서 가장 처음으로 x보다 같거나 작아지는 인덱스
    for i in range(1, n+1):
        while i*idx>x and idx>=1: #처음으로 x보다 같거나 작아지는 인덱스를 구하기 위함
            idx-=1
        if i*idx==x: #반복문이 끝났을 때 x와 같다면 same_cnt 증가
            same_cnt+=1
        elif idx<1: #idx가 1보다 작으으면 조사할 필요가 없음음
            break
        cnt+=idx #x보다 작은 것의 개수
    
    if cnt-same_cnt<k<=cnt: #조건에 부함
        print(x)
        exit()
    elif cnt-same_cnt>=k:
        x_is_greater(low, x-1)
    else:
        x_is_greater(x+1, high)
n=int(input()) 
k=int(input()) 
x_is_greater(1, n**2)