[코드트리 챌린지] 세번째 학습진단

이번엔 시간 문제로 836점에 머물렀다.

그래도 바로 전 두번째 학습진단에서 틀렸던 문제와 동일한 문제를 만났었는데,

다행이 맞춰서 넘어갈 수 있었다.

틀린 문제는 Parametric Search 문제였는데 기준 세우는 연습이 필요할 것 같다.

이분탐색을 활용하면 좋을 것 같다는 생각이 들지만 막상 안의 메서드를 세우는 방법이 어렵다고 느껴진다.

오늘은 Parametric Search 한 문제를 풀어보며 익숙해지자.

 

https://www.codetree.ai/landing/level-test/6441/result/4?&utm_source=clipboard&utm_medium=text 

문제

이차원 배열 A에 각각의 행과 열을 곱한 값이 입력되어 있는데 (인덱스는 1부터),

오름차순으로 정렬하였을 때, k번째에 나오는 수를 구하는 문제이다.

문제만 보면 정렬 문제인 것 같은데 정렬로 풀면 시간 초과가 난다.

그렇기 때문에 Parametric Search로 접근해야한다.

 

코드

n = int(input())
k = int(input())

start = 1                     # 정렬시 가장 왼쪽에 있는 값
end = n * n                   # 정렬시 가장 오른쪽에 있는 값
ans = n * n                   # 가장 큰 값에서 줄여 간다.

while start <= end:
    mid = (start + end) // 2      # 중앙값을 가정한다.
    
    temp = 0					
    for i in range(1, n + 1):     # 각 i번째 행에 대하여
        temp += min(n, mid // i)  # 중앙값(mid)보다 작거나 같은 수의 갯수는 min(n, mid // i) 이다.
                                  # 따라서 각 행에 대한 작거나 같은 숫자의 개수를 합하면 
                                  # mid값의 정렬 위치를 대략적으로 알 수 있다.
    
    if temp >= k:             # k값보다 크거나 같다면 
        end = mid - 1         # 왼쪽 범위에 답이 있다는 뜻임으로 끝 숫자를 mid-1로 바꾼다.
        ans = min(ans, mid)   
    else:
        start = mid + 1         # k값보다 작다면 오른쪽 범위 임으로 시작 숫자를 바꾼다.

# 답을 출력한다.
print(ans)

 

#코드트리 #코딩테스트 #코딩테스트실력진단