7795 먹을 것인가 먹힐 것인가

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b7795 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		while(T --> 0) {
			
			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];
			int count = 0;
			
			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());
			}
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if (A[i] > B[j]) count++;
				}
			}
			sb.append(count).append("\n");
			
			
		}
		System.out.println(sb);
		
	}

}

답은 잘 나오지만 시간 초과가 뜬다... 난관 봉착 ㅜㅜ 완전탐색이라서 시간이 많이 걸리나보다. 

 

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class b7795_2 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		while(T --> 0) {
			
			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 answer = 0;
			for(int i = 0; i < N; i++) {
				for(int j = M-1; j >= 0; j--) {
					if (A[i] > B[j]) {
						answer+=j+1;
						break;
					}
				}
			}
			sb.append(answer).append("\n");
			
			
		}
		System.out.println(sb);
		
	}

}

 

 

HOW?

 

배열 B를 소트 시키고 역순으로 for문을 돌린다.

내가 처음에 푼 방법은 모든 수를 비교하므로 시간이 당연히 오래 걸리지만 위처럼 B를 오름차순 정렬한다.

B에서 가장 큰 수(B[M-1])가 비교 대상(A[i])보다 작으면 그 이하의 수, 즉 이전 인덱스에 있는 수들(B[M-2],B[M-3], .., B[0])도 비교 대상보다 당연히 작은 것이며 만약 그 수가 비교 대상보다 크면 제외시킨다. 

따라서 하나하나 비교하는 작업을 할 필요 없고 더 간단하고 빠르게 코드를 구현할 수 있음. 

*이분탐색 !! *