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])도 비교 대상보다 당연히 작은 것이며 만약 그 수가 비교 대상보다 크면 제외시킨다.
따라서 하나하나 비교하는 작업을 할 필요 없고 더 간단하고 빠르게 코드를 구현할 수 있음.
*이분탐색 !! *
'Problems & Solutions' 카테고리의 다른 글
1920 수 찾기 (0) | 2022.08.05 |
---|---|
19941 햄버거 분배 (0) | 2022.08.05 |
9095 1, 2, 3 더하기 (0) | 2022.07.30 |
11441 합 구하기 (0) | 2022.07.26 |
1058 친구 (0) | 2022.07.25 |