[백준] 1300 - K번째 수 🖋️ (Python) / 골드 2 / 이분 탐색

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

요약 하자면, 첫줄에 배열의 크기 N이 주어지고 다음줄에 k가 주어집니다. 그러면 NxN 배열 A를 1차원 배열로 만들고 오름차순으로 정렬한 배열을 B라고 할 때, B[k]를 출력해야 합니다. 이 때, NxN 배열 A는 A[i][j] = ixj로 원소들이 있습니다. 예를들어 1행 1열은 1, 1행 2열은 2 이렇게 값이 들어있습니다.

1) 예제 입출력❄️

예제 입출력

2. 핵심 논리☢️

NxN행렬을 1열로 펴지 않고, 각 행에서 trg_value(타겟 값)이하인 수의 개수가 곧 타겟 값의 인덱스임을 이용해서 이분탐색을 하는것이 핵심입니다. 이 때, estimated_idx를 이분 탐색하여 trg_value를 찾기 때문에 result = trg_value를 갱신해 가며, 이분탐색을 끝까지 해서 while문이 종료될 때의 result를 출력합니다.

3. 풀이 코드✅

1) 코드

N=int(input())
k=int(input())

s,e = 1,N*N
while s <= e:
    trg_value = (s+e)//2
    estimated_idx = sum(min(trg_value//i,N) for i in range(1,N+1))
    if estimated_idx >= k:
        result = trg_value
        e = trg_value-1
    else:
        s = trg_value+1
        
print(result)

배열의 크기 N이 주어지고 다음줄에 k가 주어집니다. B[k]의 값을 찾는 값(trg_value)로 두고 이분 탐색을 진행합니다. 범위는 1부터 N 제곱까지 입니다. trg_value의 인덱스는 1부터 시작하므로, 배열에서 trg_value 이하의 숫자들의 개수를 모두 세면 그것이 곧 trg_value의 추정 인덱스(estimated_idx)가 됩니다. estimated_idx가 k이상일 때는 배열 B에 대해 인덱스를 오른쪽에서 왼쪽으로 찾는 방향입니다. 배열 B에는 똑같은 값이 여러개 있을 수 있으므로, 추정인덱스가 딱 이분탐색으로 찾아지지 않을 수 있습니다. 그렇기 때문에 k 이상일 때, result = trg_value를 갱신해 줌으로써, 추정인덱스를 못찾더라도, 이분 탐색이 종료되어 while문이 끝나게 되면, result에는 항상 B[k]의 값이 저장되게 됩니다. 

즉, 값이 여러개일 수 있기 때문에, 정확한 인덱스는 못찾아도 이분탐색이 종료될 때, result의 값은 B[k]를 보장합니다. 이는 주어진 예제 입 출력 1  에서 이분탐색 과정에서 마지막에 estimated_idx는 8로 종료되지만, B[7]도 6이고, B[8]도 6이기 때문에 정답 6이 출력되는 것 입니다.

2) 주석 달린 코드

N=int(input()) # 배열의 크기 N
k=int(input()) # 배열을 flatten했을 때, 출력해야할 인덱스

s,e = 1,N*N # 이분탐색 시작 1~N*N (시작인덱스가 1부터)
while s <= e:
    trg_value = (s+e)//2 # B[k]값으로 찾아야할 타겟 값
    # 각 행에서 trg_value이하인 값들의 개수 → 추정 인덱스
    estimated_idx = sum(min(trg_value//i,N) for i in range(1,N+1))
    if estimated_idx >= k: # 추정 인덱스가 찾는 인덱스보다 크거나 같으면
        e = trg_value-1 # 더 작은쪽(왼쪽)을 봐야되서 end를 땡겨온다.
        result = trg_value # 추정 인덱스가 찾는 인덱스보다 컸다가, 작아지는 방향에서 s와e가 같아지면 trg_value가 같은 왼쪽에 있는 인덱스가 찾는 인덱스
    else: # 추정 인덱스가 찾는 인덱스(k)보다 작으면 
        s = trg_value+1 # 오른쪽(큰쪽) 보기
        
print(result)

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1300_k%EB%B2%88%EC%A7%B8_%EC%88%98.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/