(https://www.acmicpc.net/problem/7795)

접근 방법 🧐

이분탐색 문제인 것은 알지만, 이분탐색이 아니어도 풀 수 있을 것 같아서 두가지 방법으로 풀어봤다.

1. 이분탐색 O

• B를 오름차순으로 정렬한다.
  
  

2. 이분탐색 X

• A와 B 둘다 내림차순 정렬
  
  
• A가 B보다 더 큰 값을 발견하면 그 다음 숫자들은 당연히 크니까 결과에 값 더하고 break;
  
  
• 더 큰 값이 나오지 않으면, 모든 값들을 다 비교해야해서 시간초과가 나올것 같았지만, 범위가 작아서 해볼만해보인다.

내가 쓴 코드 ✍️

1. 이분탐색 O

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

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder result = new StringBuilder();
		int T = Integer.parseInt(br.readLine()); //테스트케이스 수
		
		for(int t=0;t<T;t++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			int[] A = new int[N];
			int[] B = new int[M];
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(B);
			int temp = 0;
			for(int i=0;i<N;i++) {
				int low = 0;
				int high = M-1;
				int cnt = 0;
				while(low<=high) {
					int mid = (low+high)/2; //중간값
					if(B[mid]<A[i]) {
						low = mid+1;
						cnt = mid+1;
					}
					else
						high = mid-1;
				}
				temp+=cnt;
			}
			result.append(temp+"\n");
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}
}

2. 이분탐색 X

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

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder result = new StringBuilder();
		int T = Integer.parseInt(br.readLine()); //테스트케이스 수
		
		for(int t=0;t<T;t++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			Integer[] A = new Integer[N];
			Integer[] B = new Integer[M];
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(A,Collections.reverseOrder());
			Arrays.sort(B, Collections.reverseOrder());
			int temp = 0;
			for(int i=0;i<N;i++) {
				int cnt = 0;
				for(int j=0;j<M;j++) {
					if(A[i]>B[j]) {
						temp+=(M-cnt);
						break;
					}
					else cnt++;
				}
			}
			result.append(temp+"\n");
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}
}

---

느낀점 📖

시간이 무려 5배이상 차이난다...!!