값을 배열에 넣고 정렬를 하면 배열의 크기가 최대 10^10이 되므로 메모리초과가 나온다. 따러서 다른 방향으로 풀어야한다
그림은 문제의 예제를 기준으로 한다.
B 배열이 정렬되어있는 상태라면 B[7] = 6은 6보다 작거나 같은 원소의 개수는 7개라는 의미이다. 즉 B[k] = x라고 한다면 k값이 주어졌으니 B[7]= x 로 x의 값을 찾으면된다. 어떻게 찾아야할까?
이진탐색을 이용하면 된다.
x의 범위는 1< x< k이다. (왜 n*n이 아닌지 모르겠음~)
- 범위가
1< x< 7일때 mid는 4이다. 즉b[k] = 4일때 4보다 작거나 같은 원소의 개수는 총 k개이고 계산해보면 6개이다.b[6] = 4이고 6(cnt)이 7(k)보다 작으므로 범위를 수정한다.low= mid +1로 수정해서 범위를 좁힌다. - 범위가
5 < x< 7일때, mid는 6, 즉 b[k]= 6일때 6보다 작거나 같은 원소의 개수는 총 k개이고 8개이다.b[8] = 6이고 , 8(cnt)가 7(k)보다 크므로 범위를 수정한다.high = mid -1으로 범위를 수정한다. - 범위가
5< x < 5일때, mid는 5 , 즉 B[k] = 5일때 5보다 작거나 같은 원소의 개수는 총 k개이고 계산하면 5개이다.b[5] = 5이므로, 5(cnt) 가 7(k)보다 크므로 범위를 수정한다.high = mid -1로 범위를 수정한다. - high가 5-1 = 4, low는 5가 되므로 low가 high보다 크므로 for문이 끝난다.
k개를 구하는 방법은 다음과 같다. 그림의 2차원 배열을 잘 보면 규칙이 존재하는데 구구단 1단, 2단, 3단이라는 규칙을 갖고있다. 만약 내가 구구단에서 3보다 작거나 같은 값을 구하고자 한다면
1단 : 3/1 = 3 이므로 총 3개
2단 : 3/2 = 1 이므로 총 1개
3단: 3/3 = 1 이므로 총 1개
즉 구하고자하는 값에 단을 나누면 값이 나온다.
다만 범위가 3까지 존재하는데 내가 구하고자 하는 값이 5라면 5/1= 5가 나온다. 구하고자 하는 값이 클수있으므로 Math.*min*(mid / i, n) 이렇게 최소값을 찾는 과정을 추가해서 값을 구해야한다.
문제를 주의해야할점은 인덱스를 알고있으므로 인덱스의 값을 가정해 (=mid) , 인덱스를 구하고, 인덱스와 주어진 K값을 비교해가면서 인덱스와 k 값과 같을때까지 반복하는 문제이다.