문제 요약
- 알고리즘 분류: 이분탐색
- 난이도: Gold2
- 문제내용:
- 크기 N×N 배열이고 시작 인덱스는 0이 아니고 1부터 시작한다.
- 배열 A[i][j]의 값은 i × j이다.
- 2차원 배열 A를 일차원 배열 B로 만들어서 오름차순으로 정렬하면 배열 B에서 K번째 인덱스 값을 구해라
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
문제풀이
이번 문제는 간단해 보일거 같은데.. 배열 A에서 완전탐색으로 값을 넣고 B로 일렬로 만들어서 정렬한다음 K번째 인덱스 위치 값 반환 이런식으로 풀면 N의 크기가 10만이고 시간복잡도는 O(N ^ 2)이므로 시간 초과가 날것이다. 저 문제를 풀라면 O(logN)시간안에 풀어야 통과가 된다. 그래서 이번 문제의 핵심 알고리즘 O(logN)으로 풀수 있는 이분 탐색이다. 이분탐색의 자세한 설명은 아래 사이트에서 확인 하면된다.
https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89
이진 탐색 - 나무위키
이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권
namu.wiki
문제 접근 방법
예제를 위 표로 표현 한것이다. 왼쪽은 A 배열이라고 하고 오른쪽은 A배열을 일차원으로 변경후 오름차순으로 정렬한 B배열이라고 보면 오른쪽의 표를 보면 인덱스의 위치 와 값을 비교해보면 인덱스 위치 <= 값 이라고 볼 수가 있다. 그렇다고 인덱스 위치 <= 값 이 내용만으로도 이분탐색 하기는 힘들다. 그래서 그 다음으로 봐야 할것은 값의 순위를 봐야 한다.
- 1 보다 이하인 수: 1개
- 2 이하인 수 : 3개
- 3 이하인 수 : 5개
- 4 이하인 수 : 6개
- 5 이하인 수 : 6개
- 6 이하인 수 : 8개
- 7 이하인 수: 8개
- 8 이하인 수: 8개
- 9 이하인 수: 10개
예제에서 찾고 싶은 인덱스는 7이다. 하지만 A 배열에서 7라는 수는 없다. 그래서 위에 7이하인 개수가 8개이고 같은 8개중 가장 낮은 숫자가 6이다. 그래서 결론은 동일한 개수 중 가장 낮은 수는 A 배열에 존재 한다는 것을 알수 있다. 그 이유는 개수가 변화되는 시점이고 변화가 될려고 하면 배열안에 값은 무조건 있어야 된다는 것이다. 그래도 이해가 안되면 N과 K를 다른 수를 예시로 해서 A4용지에 문제 접근 방법 처럼하면 알 수 가 있다. 이 내용을 이해가 되면 다음에는 개수를 구하는 방법을 알면 된다.
일 단 A 배열은 1 ~ N 까지의 구구단이라고 생각하면되고 중간 값을 value라고 하면 각 행마다 현재 값보다 낮은 개수(value/ 행 번호 = j의 위치 반환)를 더하면된다. 하지만 각 행의 최대 개수는 N이라서 (value/ 행 번호 > N)크면 범위가 넘어가서 넘어간 경우에는 N이라고 하면된다. 그래서 결론으로는 min(value / 행 번호, N)이런 식으로 된다. 그 다음에는 K의 수가 중간값의 개수보다 낮은면 start 값을 m + 1로 하고 크거나 같으면 end 값을 m - 1로 범위를 줄이면서 탐색 하면된다.
정리
- start는 1(인덱스 1부터 시작해서 1로 세팅함) end는 N * N으로 설정한다.
- 중간값이하의 개수를 구한다.
- 중간값이하의 개수보다 작으면 start값은 m - 1, 중간값보다 크거나 같은면 m + 1로 값을 설정 한다.
- 값의 범위가 1로 될때 start값을 출력하면된다.
Code
Python
N = int(input())
K = int(input())
start = 0
end = N * N
while start <= end:
mid = (start + end) //2
count = 0
for i in range(1, N + 1):
count += min(mid // i, N)
if count >= K :
end = mid - 1
else:
start = mid + 1
print(start)
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
long K = Long.parseLong(br.readLine());
long start = 1;
long end = N * N;
long mid, count, i;
while(start <= end) {
mid = (start + end) / 2;
count = 0;
for(i = 1; i <= N; i++) {
count += Math.min(mid / i, N);
}
if(count >= K) {
end = mid -1;
}else {
start = mid + 1;
}
}
System.out.println(start);
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BAEKJOON] 12015 가장 긴 증가하는 부분 수열 2 (2) | 2022.11.29 |
---|---|
[BAEKJOON] 22193 Multiply (0) | 2022.11.28 |
[BAEKJOON] 2012 등수 매기기 (0) | 2022.11.28 |
[BAEKJOON] 6549 히스토그램에서 가장 큰 직사각형 (0) | 2022.11.25 |
[BAEKJOON] 1439 뒤집기 (0) | 2022.11.25 |