[yukicoder] No.647 明太子

アルゴリズムの問題を解く

今日もアルゴリズムの問題の問題を解いてみました。

問題文

No.647 明太子 - yukicoder

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Mentaiko {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int []A = new int[N];
        int []B = new int[N];
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < 2 * N; i++){
            int k = scanner.nextInt();
            if(i % 2 == 0) {
                A[count1] = k;
                count1++;
            }else if(i % 2 == 1){
                B[count2] = k;
                count2++;
            }
        }
        int M = scanner.nextInt();
        int []X = new int[M];
        int []Y = new int[M];
        int count3 = 0;
        int count4 = 0;
        for(int i = 0; i < 2 * M; i++){
            int k = scanner.nextInt();
            if(i % 2 == 0) {
                X[count3] = k;
                count3++;
            }else if(i % 2 == 1){
                Y[count4] = k;
                count4++;
            }
        }
        scanner.close();
        int []sumM = new int[M];
        Arrays.fill(sumM, 0);

//     for(int i = 0; i < N; i++) {
//         System.out.println(A[i] + ", " + B[i]);
//     }
//     for(int i = 0; i < M; i++) {
//     System.out.println(X[i] + ", " + Y[i]);
// }

        int flag = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(X[j] <= A[i] && Y[j] >= B[i]) {
                    sumM[j]++;
                    flag++;
                }
            }
        }
        // 該当なし
        if(flag == 0) {
            System.out.println("0");
            System.exit(0);
        }
//     for(int i = 0; i < M; i++) {
//         System.out.println(sumM[i]);
//     }
        int k = 0;
        int max = sumM[0];
        int ans = 0;
        ArrayList<Integer> array = new ArrayList<Integer>();
        for(int i = 0; i < M; i++) {
            k = sumM[i];
            if(k == max) {
                array.add(i + 1);
                ans = i + 1;
            }else if(k > max) {
                max = k;
                ans = i + 1;
                array.clear();
            }
        }
        if(array.size() > 1) {
            for(int i = 0; i < array.size(); i++) {
                System.out.println(array.get(i));
            }
        }else if(max != 0){
            System.out.println(ans);
        }
    }
}

感想

この問題の肝は、最大値とその要素番号を取得することだと思います。 最大値が重複する可能性があるので、要素番号を保持しなければならないと思います。

因みに僕だったら、A = 1, B = 1ですかね。 明太子はあまり得意ではありません(´・ω・`)