[boj] 1300_K번째 수_python

문제링크

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

1300번: K번째 수

 

---

 

문제설명

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

 

입력

1. 배열의 크기 N이 주어진다.

2. k가 주어진다

 

출력

1. 일차원 배열 B를 오름차순 정렬했을 때 나오는 B[k] 

 

제한

• 배열 A와 B의 인덱스는 1부터 시작한다.
• 구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.
• .N은 N <= 10^5 인 자연수 
• k는 min(10^9, N^2)인 자연수

---

비슷한 문제

paramertric search를 하는 다른 문제인 랜선 자르기와 비슷한 문제였다. 

랜선 자르기 같은 경우에는 주어진 N개의 랜선에서 뽑아낼 수 있는 K개의 공통 최대 랜선 길이를 출력하는 문제였다.

# https://www.acmicpc.net/problem/1654
import sys
sys.setrecursionlimit(10**7)
input, _list = sys.stdin.readline, []
N, K = map(int, input().split())
for i in range(N):
    t = int(input())
    _list.append(t)
_list.sort()
def parametical_search(s, e):
    if s <= e:
        cnt = 0
        mid = (s + e) // 2
        for i in range(N):
            cnt += ( _list[i] // mid )
        if cnt >= K:
            return parametical_search(mid+1, e)
        else:
            return parametical_search(s, mid-1)
    return e
print(parametical_search(1, _list[-1]))

---

문제풀이

시간 복잡도 :parametric_search O( 2 log₂ N ) * cnt갱신 O(N) => O( N log₂ N )

공간 복잡도 : parametric_search O(  2 log₂ N  ) (재귀로 인한 복잡도)

 

위에서 살펴본 랜선 자르기에서는 공통의 최대 길이를 출력하기 위해 

cnt += _list[i] // mid

와 같은 과정을 진행하며 _list[i] 번째 길이에 해당하는 랜선에서 뽑아낼 수 있는 서브 랜선의 개수를 얻어내었다.

 

K번째 수 같은 경우에는

cnt += min(mid // i, N)

과 같은 과정을 진행하여 cnt에 mid보다 작은 수의 개수를 저장한다.

 

mid보다 작은 수의 개수는 mid번째 수를 찾을 수 있게 해주고

이를 K와 비교하여 결론적으로 K번째 수를 얻을 수 있도록 해준다.

 

import sys # 재귀 깊이, 빠른 입출력을 위해 사용
sys.setrecursionlimit(10 ** 8)
input, print= sys.stdin.readline, sys.stdout.write
# 배열의 크기 N과, B[k]를 구하기 위한 수 K
N = int(input())
K = int(input())

def parametric_search(s,e):
	# K번째 수를 찾은 경우 그 값을 출력한다.
    if s >= e:
        return s
    # cnt : 구간 [1, N+1)에 해당하는 범위에 존재하는 수의 개수
    # cnt : mid^2 이하를 가지는 수의 개수, 즉 mid^2번째(K번째) 수를 의미
    # mid : A[i][j] = i * j를 성립하게 하기 위함
    cnt = 0
    mid = (s + e) // 2
    # N과 mid // i를 진행하여 더 작은 값을 cnt에 더해준다.
    # 이 과정을 통해 mid보다 작은 범위에 존재하는 수의 개수, cnt를 알 수 있다. 
    for i in range(1,N+1):
        cnt += min(mid//i, N)
    # cnt가 K보다 큰 경우 right를 작게 만듦
    if cnt >= K:
        return parametric_search(s, mid)
    # cnt가 K보다 작은 경우 left를 크게 만듦
    else:
        return parametric_search(mid+1, e)
# parametric_search의 결과 출력
print(str(parametric_search(1, N*N)) + "\n")

 

---

어려웠던 점

구하기 귀찮아서 heapq의 nsmallist를 사용하여 k번째 수를 구하려고 했지만

메모리 초과를 반환했다.

 

그를 방지 하기 위해 gc(garbage collector)를 사용했지만

그 다음엔 시간 초과를 반환하였다.

import sys, heapq, gc
input, print = sys.stdin.readline, sys.stdout.write
N = int(input())
K = int(input())
T = 0
_list = []
heapq.heapify(_list)
for i in range(1,N+1):
    for j in range(1,N+1):
        heapq.heappush(_list, i*j)
        gc.collect()

B = heapq.nsmallest(K, _list)
print(str(B[-1])+ "\n")

 

주어진 문제는 주어진 방식대로 푸는 게 낫다는 것을 깨닫게 된 시간이었다.