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 로 끝을 낸다.

 

 

보다시피 코드가 뭔가 너무 복잡하다.

 

다른 사람 코드를 보니, 너무 복잡하다는 게 느껴졌다.

 

다음 블로그 자료를 참고해서 공부를 더 해야 할 듯 하다.

 

https://coder-in-war.tistory.com/entry/BOJ-JAVA7795-%EB%A8%B9%EC%9D%84-%EA%B2%83%EC%9D%B8%EA%B0%80-%EB%A8%B9%ED%9E%90-%EA%B2%83%EC%9D%B8%EA%B0%80

[ BOJ ][JAVA][7795] 먹을 것인가 먹힐 것인가