7795 먹을 것인가 먹힐 것인가 (java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int one;
static int two;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
one = Integer.parseInt(st.nextToken());
two = Integer.parseInt(st.nextToken());
int A [] = new int [one];
int B [] = new int [two];
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
for(int j =0 ; j<one; j++) {
A[j] = Integer.parseInt(st1.nextToken());
}
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for(int j =0 ; j<two; j++) {
B[j] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(A);
Arrays.sort(B);
System.out.println(search(A,B));
}
}
public static int search(int A [], int B[]) {
int count=0;
for(int i=0; i<one; i++) {
int number = A[i];
int left = 0;
int right = two-1;
while(true) {
// 4
if(right < left) {
if(number<B[right]) {
count+=left+1;
break;
}else if(number==B[right]) {
count+=left;
break;
}
}
// 1
if(number>B[right]) {
count+= right+1;
break;
}
// 2
if(number<= B[left]) {
count+=left;
break;
}
// 3
if(number>B[left]) {
if(number <= B[right]) {
int mid = (left + right)/2;
if(number<= B[mid]) {
right = mid-1;
}else if(number>B[mid]) {
left = mid+1;
}
}
}
}
}
return count;
}
}
울며 겨자먹기 식으로 맞았다 ㅠㅠ
그래도 노력의 과정은 남기는 것이 좋을 것 같아서 기록으로 남기려 한다.
보통 이분 탐색에서 mid, left, right 를 사용하는데, 이 코드에서는 배열의 인덱스에 mid, right, left 를 적용했다.
이분탐색의 경우는 보통 배열을 오름차순 정렬해서 사용한다.
그래서 하나의 예를 들어 설명하겠다.
첫번째 배열을 A 라 하고, 1 3 5 7 10 이다.
두번째 배열을 B 라 하고, 3 3 4 5 6 8 9 이다.
즉, A의 각 원소들이 B의 각 원소들보다 큰 가짓수를 세면 15가지이다.
이 과정을 코드로 보자면,
먼저 배열 A의 원소와 B의 원소를 비교하면 3가지 경우가 나온다.
A의 원소 중 하나를 a라 하고,
B의 원소가 세가지, b c d 가 있다고 하자.
1) a > d (a가 b,c,d 보다 크다.)
위의 코드에서 // 1 부분
2) a <= b (a 가 b,c,d 보다 작다. b랑 같은 경우도 포함한다.)
위의 코드에서 // 2 부분
3) b < a < d (a가 b ~ d 범위 내에 있다.)
위의 코드에서 // 3 부분
예를 들어 설명하겠다.
위의
A : 1 3 5 7 10
B : 3 3 4 5 6 8 9
배열에서 설명한다.
1) 의 경우
A의 원소중 10 (a) 이, B의 원소 중 제일 큰 9 (d)보다 크다. 즉, a > d
코드에서는 아래와 같이 표현되고 있다.
// 1
if(number>B[right]) {
count+= right+1;
break;
}
맨 처음 right = 6이다.
right 는 B 배열의 제일 오른쪽 인덱스를 표현한다.
(인덱스가 0부터 시작된다.)
number = 10
10 > 9 이므로 이런 경우는 바로 9의 인덱스인, 6보다 1개 더 큰 7을 리턴하면 끝난다.
즉, 10은 B의 원소 3 3 4 5 6 8 9 보다 크므로 7개가 리턴되는 것이다.
2)의 경우
A의 원소 중 3 (a) 이, B의 원소 중 제일 작은 3 (b) 과 같다. 즉, a <= b
// 2
if(number<= B[left]) {
count+=left;
break;
}
number = 3
이 경우 left 값은, 즉 B원소 중 제일 작은 3의 인덱스로, 0이므로,
number < = B[left] 를 만족하고,
count 에는 0이 추가 되서, 결과적으로 0이 리턴된다.
위의 2가지 예처럼 쉬운 것들만 있다면 좋겠지만,
그렇지 않다.
즉, 여기서 A 원소 10이 B 원소들보다 크다는 게 한 눈에 보여서 바로 count 값을 찾아서 리턴할 수 있지만,
이분분할을 여러 번 한 뒤에야 1)의 경우를 만족해서 그때서야 count 값을 찾을 수 있는 경우도 있다.
아래에서 설명하겠다.
3) 의 경우 - 1)의 경우와 함께
A의 원소 중 5(a) 를 보자.
B : 3 3 4 5 6 8 9 중에서 제일 작은 3보다는 크고, 제일 큰 9보다는 작다.
3(b) < 5(a) < 9(d) 를 만족하는 경우이다.
이 경우는 아래처럼 분할을 해준다.
// 3
if(number>B[left]) {
if(number <= B[right]) {
int mid = (left + right)/2;
if(number<= B[mid]) {
right = mid-1;
}else if(number>B[mid]) {
left = mid+1;
}
}
}number = 5, B[left] = 3, B[right] = 9
number > B[left] 이고, number <= B[right] 를 만족하기 때문에,
left = 0, right = 6에서,
mid = 3이다.
B[mid] = 5
그런데,number <= B[mid] 이므로,
right = 2 가 된다.
그러면, B[right]= 4 이므로,
// 1
if(number>B[right]) {
count+= right+1;
break;
}
number > B[right] 를 만족하므로,
count 에다가 right + 1 을 해서,
즉 3을 반환하면 된다.
이처럼 이분분할을 한 다음에는, //4, //1, //2 의 경우 중에 한 가지 상황이 완성되기 때문에 이 중에서 count 값을 반환한 뒤 break 로 끝을 낸다.
보다시피 코드가 뭔가 너무 복잡하다.
다른 사람 코드를 보니, 너무 복잡하다는 게 느껴졌다.
다음 블로그 자료를 참고해서 공부를 더 해야 할 듯 하다.
[ BOJ ][JAVA][7795] 먹을 것인가 먹힐 것인가
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가
coder-in-war.tistory.com