[알고리즘] 먹을 것인가 먹힐 것인가 - Two Point

내 풀이

public class Main {
    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());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int[] arr1 = new int[A];
            int[] arr2 = new int[B];

            st = new StringTokenizer(br.readLine());
            for (int a = 0; a < arr1.length; a++){
                arr1[a] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int b = 0; b < arr2.length; b++){
                arr2[b] = Integer.parseInt(st.nextToken());
            }

            solution(arr1, arr2);
        }

    }

    private static void solution(int[] arr1, int[] arr2) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int num : arr1){
            int start = 0;
            int end = arr2.length - 1;
            while (start <= end){
                if (num > arr2[start]){
                    count++;
                }

                if (start != end){
                    if (num > arr2[end]) {
                        count++;
                        end--;
                    }
                }
                start++;
            }
        }

        sb.append(count).append("\n");
        System.out.print(sb.toString());
    }
}

• start와 end를 투 포인터로 설정
• while문을 start가 end보다 커질 때까지 반복
• arr1의 값을 받아와 arr2의 맨 앞과 뒤를 비교
• if (start != end) 사용한 이유는 start와 end가 같을 경우 count가 2증가하게 되므로 end 부분은 start와 end가 같지 않을 경우만 수행
• 실행시간 (2946ms)

다른 사람 풀이

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

public class P7795 {
    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());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int[] arr1 = new int[A];
            int[] arr2 = new int[B];

            st = new StringTokenizer(br.readLine());
            for (int a = 0; a < arr1.length; a++){
                arr1[a] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int b = 0; b < arr2.length; b++){
                arr2[b] = Integer.parseInt(st.nextToken());
            }

            solution(arr1, arr2);
        }

    }

    private static void solution(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);

        int count = 0;
        for (int num : arr1){
            int idx = lowerBound(arr2, arr2.length, num);
                count += idx;
            }

        System.out.println(count);
    }

    private static int lowerBound(int[] arr2, int length, int num) {
        int start = 0;
        int end = length;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr2[mid] >= num){
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}

• arr2의 값과 길이, target숫자를 보내준다.
• start가 end랑 같거나 클때까지 반복한다
• mid를 설정하여 내부 for문을 없앤것이 가장 큰 차이
• mid가 num보다 크다면 왼쪽으로 이동
• mid보다 num이 크다면 오른쪽으로 이동하게 하였다.
• 실행 시간(468ms)