문제 링크
12991번: 홍준이의 행렬
홍준이에게는 길이가 N인 수열 2개 A와 B가 있습니다. 이때 N2 크기의 행렬을 만드는데, 행렬의 i행 j열의 원소는 수열 A의 i번째 원소와 수열 B의 j번째 원소의 곱으로 정의합니다. 홍준이는 이 원
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 길이가 N인 수열 A와 B가 있습니다.
2. N² 크기의 행렬을 만들 때 (i, j)의 원소는 "A의 i번째 수 × B의 j번째 수"입니다.
3. N² 행렬에서 K번째로 작은 수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 2번의 이분탐색을 통해서 K번째 작은 수를 탐색합니다.
3. 탐색한 K번째 작은 수를 결과로 출력합니다.
1번째 이분탐색(0 ~ 배열의 최대값, K번째 작은값에 가까운 값 탐색)
배열의 최대값 : A수열의 최대값 × B 수열의 최대값
수열의 최대값이 10억이기 때문에 10억 × 10억은 int을 벗어나기 때문에 long으로 관리해야 합니다.
이분 탐색을 진행하면 mid값보다 작은 값이 몇 개 있는지 확인합니다.
작은 값의 개수에 따라 탐색하는 범위를 변화시킵니다.
1. 작은 값의 개수 < K
해당 값보다 더 큰 범위를 탐색해야 합니다.
Start = mid + 1
2. 작은 값의 개수 > K
해당 값보다 더 작은 범위를 탐색해야 합니다.
Start = mid + 1
3. 작은 값의 개수 == K
현재 값보다 작은 값의 개수가 K이기 때문에
작은 값 중에 가장 큰 값이 K번째 수가 됩니다.
탐색 종료!
2번째 이분탐색(1번째 이분탐색 mid보다 작은 수 개수 구하기)
※ 2번째 이분탐색을 진행하기 전에 A수열과 B수열은 오름차순으로 정렬되어 있어야 합니다.
A수열을 완전탐색으로 각 수를 선택한 뒤,
B수열에 대해서 이분탐색을 통해서 작은 값의 개수를 탐색합니다.
1. mid값이 가리키는 수열 B의 값 × A수열의 현재 값 ≤ 1번째 이분탐색 mid값
start = mid + 1;
2. mid값이 가리키는 수열 B의 값 × A수열의 현재 값 > 1번째 이분탐색 mid값
end = mid - 1;
현재 수열 A의 값에 대해서 작은 값의 개수를 모두 더해서 결과로 반환합니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 2
K : 3
수열 A : { 2, 3 }
수열 B : { 3, 5 }
2. 2번의 이분탐색을 통해서 K번째 작은 수를 탐색합니다.
수열 오름차순 정렬
수열 A : { 2, 3 }, 최대값 : 3
수열 B : { 3, 5 }, 최대값 : 5
행렬의 최대값 : 3 × 5 = 15
1번째 이분탐색 진행
Start : 0
End : 15
mid : 7
mid보다 작은 개수 구하는 이분탐색 진행
A가 가리키는 수열의 값이 2일 때
Start = 0
End = 1(N-1)
mid = 0
mid값이 가리키는 수열 B의 값(3) × A수열의 현재 값(2) ≤ 1번째 이분탐색 mid값(7)
start = mid + 1 : 1
다음 탐색
Start = 1
End = 1
mid = 1
mid값이 가리키는 수열 B의 값(5) × A수열의 현재 값(2) > 1번째 이분탐색 mid값(7)
end = mid - 1 : 0
start ≤ end가 False임으로 이분탐색 종료
작은 값 개수 + start : 0 + 1 = 1
A가 가리키는 수열의 값이 3일 때
Start = 0
End = 1(N-1)
mid = 0
mid값이 가리키는 수열 B의 값(3) × A수열의 현재 값(3) > 1번째 이분탐색 mid값(7)
end = mid - 1 : 0
start ≤ end가 False임으로 이분탐색 종료
작은 값 개수 + start : 1 + 0 = 1
2번째 이분탐색 종료 : 1번째 mid값보다 작은 값은 1개
작은 값의 개수(1개) < K
start = mid + 1 : 8
2번째 이분탐색 진행
Start : 8
End : 15
mid : 11
mid보다 작은 개수 구하는 이분탐색 진행
A가 가리키는 수열의 값이 2일 때
Start = 0
End = 1(N-1)
mid = 0
mid값이 가리키는 수열 B의 값(3) × A수열의 현재 값(2) ≤ 1번째 이분탐색 mid값(11)
start = mid + 1 : 1
다음 탐색
Start = 1
End = 1
mid = 1
mid값이 가리키는 수열 B의 값(5) × A수열의 현재 값(2) ≤ 1번째 이분탐색 mid값(11)
start = mid + 1 : 2
start ≤ end가 False임으로 이분탐색 종료
작은 값 개수 + start : 0 + 2 = 2
A가 가리키는 수열의 값이 3일 때
Start = 0
End = 1(N-1)
mid = 0
mid값이 가리키는 수열 B의 값(3) × A수열의 현재 값(3) ≤ 1번째 이분탐색 mid값(11)
start = mid + 1 : 1
다음 탐색
Start = 1
End = 1
mid = 1
mid값이 가리키는 수열 B의 값(5) × A수열의 현재 값(3) > 1번째 이분탐색 mid값(11)
end = mid - 1 : 0
start ≤ end가 False임으로 이분탐색 종료
작은 값 개수 + start : 2 + 1 = 3
2번째 이분탐색 종료 : 1번째 mid값보다 작은 값은 3개
작은 값의 개수(1개) == K
탐색 종료!
2번째 이분탐색을 할 때 최소값 : 2 × 5 = 10
3. 탐색한 K번째 작은 수를 결과로 출력합니다.
탐색으로 얻은 3번째 작은 수 : 10
10을 결과로 출력 합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 수열의 정보를 띄어쓰기 기준 저장합니다.
- 두 수열을 오름차순 정렬 및 최대값으로 행렬의 최대값을 계산합니다.
- search함수를 통해서 K번째 작은 값을 탐색합니다.
- 탐색을 통해 얻은 K번째 작은 값을 BufferedWriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 이분탐색을 통해서 K번째 작은 수에 가장 가까운 수를 탐색합니다.
- check함수는 이분탐색을 통해서 search함수에서 얻은 mid값보다 작은 수의 개수를 탐색합니다.
- arrayInput은 수열에 대한 정보를 배열에 저장하는 함수입니다.
결과코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static long result;
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] A = new int[N];
int[] B = new int[N];
//입력값 저장 및 최대값 구하기
int aMax = arrayInput(A, new StringTokenizer(br.readLine()," "), N);
int bMax = arrayInput(B, new StringTokenizer(br.readLine()," "), N);
//오름차순 정렬
Arrays.sort(A);
Arrays.sort(B);
//행렬 최대값 계산
long max = (long)aMax * bMax;
//1번째 이분탐색 진행
search(A, B, N, K, max);
//K번째 작은 값 BufferedWriter 저장
bw.write(String.valueOf(result));
bw.flush(); //결과 출력
bw.close();
br.close();
}
//1번째 이분탐색을 진행하며, K번째 가장 가까운 값을 탐색
static void search(int[] A, int[] B, int N, int K, long max){
long start = 0;
long end = max; //행렬의 최대값
//이분탐색 진행
while(start <= end){
long mid = (start + end) / 2;
//2번째 이분탐색으로 mid값보다 작은 값의 개수 구하기
int count = check(A, B, N, K, mid);
//K번째 수 찾았을 때
if(count == K){
return; //탐색 종료
}else if(count < K){ //K번째 수보다 큰 수일 때
start = mid + 1; //더 큰 범위로 설정
}else{ //K번째 수보다 작은 수일 때
end = mid - 1; //더 작은 범위로 설정
}
}
}
//2번째 이분탐색을 진행하며, 작은 값 개수 구하는 함수
static int check(int[] A, int[] B, int N, int K, long val){
int count = 0;
result = 0;
//수열 A는 완전 탐색
for(int i=0;i<N;i++){
int start = 0;
int end = N-1;
//B에 대해서 이분탐색으로 작은 값 개수 구하기
while(start <= end){
int mid = (start + end) / 2;
//현재 값 기준 곱할 때 작은 값일 때
if((long)A[i] * B[mid] <= val) {
start = mid + 1;
}else{ //현재 값 기준 곱할 때 큰 값일 때
end = mid - 1;
}
}
//작은 값이 존재할 때
if(start > 0){
//최대값 계산해두기
result = Math.max(result, (long)A[i] * B[start-1]);
}
count += start; //작은 값 개수 더하기
}
return count;
}
//배열 입력값 저장 및 최대값 반환하는 함수
static int arrayInput(int[] arr, StringTokenizer st, int N){
int max = 0;
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(st.nextToken());
//최대값 비교
max = Math.max(max, arr[i]);
}
return max;
}
}'백준' 카테고리의 다른 글
| [백준, Java] 2866번, 문자열 잘라내기(이분 탐색) (2) | 2023.12.12 |
|---|---|
| [백준, Java] 1517번, 버블 소트(세그먼트 트리) (5) | 2023.12.11 |
| [백준, Java] 1497번, 기타콘서트(백트래킹) (0) | 2023.12.09 |
| [백준, Java] 1981번, 배열에서 이동(BFS, 이분탐색) (2) | 2023.12.04 |
| [백준, Java] 13505번, 두 수 XOR(트라이, 누적합) (2) | 2023.12.02 |
댓글