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

1. 문제

7795번: 먹을 것인가 먹힐 것인가

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

---

2. 풀이

26~41번째줄까지만 보면 된다. 나머지는 전부 입력하는 부분이다.

1.  B배열을 정렬한다.

2.  A배열 요소를 하나씩 보면서 이분탐색으로 위치를 찾는다. 만약 B[m]이 a보다 크거나 같다면 h변경, 그외는 l을 변경한다.

3.  answer에 l을 더한다.

import java.io.*;
import java.util.*;

public class BOJ_7795_먹을것인가먹힐것인가 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();

      int[] A, B;
      int N,M, answer;
      StringTokenizer st;
      for(int tc=0;tc<T;tc++){
         st = new StringTokenizer(in.readLine());
         N = Integer.parseInt(st.nextToken());
         M = Integer.parseInt(st.nextToken());
         A = new int[N];
         B = new int[M];

         st = new StringTokenizer(in.readLine());
         for(int i=0;i<N;i++) A[i] = Integer.parseInt(st.nextToken());

         st = new StringTokenizer(in.readLine());
         for(int i=0;i<M;i++) B[i] = Integer.parseInt(st.nextToken());
         
         Arrays.sort(B);

         answer = 0;
         int l,h,m;
         for(int a:A){
            l = 0;
            h = M-1;
            while(l<=h){
               m = (l+h)/2;
               if(B[m]<a) l = m+1;
               else h = m-1;
            }
            answer += l;
         }

         sb.append(answer).append('\n');
      }

      System.out.print(sb);
   }
}

 

---

3. 결과

1.  Arrays의 BinarySearch를 사용했다가 틀렸다. 왜냐하면 이 메서드는 같은 요소가 여러 개 있을 때 그 중앙 idx 값을 반환하기 때문이다.

2.  이 부분에 for문을 추가했더니 맞았다. (7~10번째 줄) 하지만 하나하나 비교해야하다보니 어쩔 수 없이 시간이 오래걸렸다.

for(int a : A){
	idx = Arrays.binarySearch(B,a);
	if(idx<0) {
		idx = -idx-1;
	}
	else{
		for(int i=idx;i>=0;i--){
			if(B[idx]!=B[i]) break;
			idx = i;
		}
	}
	answer += idx;
}

3.  A,B를 모두 정렬한 뒤 A의 요소 순서대로 카운팅한다. 대신, Ai-1보다 Ai가 크기때문에 Ai-1 미리 확인해둔 곳부터 본다.

int m = 0, cnt = 0;
for(int a:A){
	while(m<M && a>B[m]){
		cnt++;
		m++;
	}
	answer+=cnt;
}

4.  본문코드다! 기본적인 이분탐색이다. 하지만 미리 정의되어있던 메서드를 사용한 게 아니라서 입맛대로 가장 첫번째 요소를 고를 수 있다.