1300 (1) 썸네일형 리스트형 [ACMICPC] 1300 . K번째 수 1300번 K번째 수 문제 보러가기 🅰 설계 1. 어떤 방법을 쓸 것인가? 문제에서 주어지는 k는 최대 10^9 = 10억이다. NxN 행렬을 만들어서 직접 정렬해보는 방법은 할 수 없다. B 행렬은 정렬되어 있다. 정렬된 상태에서 빠르게 답을 찾는 방법으로 이분 탐색을 생각해 볼 수 있다. 2. 이분 탐색을 어떻게 적용하는가? A 행렬에서 모든 행을 돌면서, 각 행에 x보다 작거나 같은 숫자를 카운트하여 그 개수가 k보다 작으면 답이 될 수 없고, k보다 크거나 같으면 답이 될 수 있다. 위 방법을 이분 탐색으로 구현하면 된다. 시간 복잡도는 행의 개수 N에 이분탐색 범위 log(N*N)을 곱해 O(N*log(N^2)) = O(2N*log(N))이 된다. 3. 전체 코드 12345678910111213.. 이전 1 다음