山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.647 明太子

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

今日もアルゴリズムの問題の問題を解いてみました。 f:id:yamakasa3:20180329174346p:plain

問題文

No.647 明太子 - yukicoder

f:id:yamakasa3:20180329174727p:plain

コード

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ですかね。 明太子はあまり得意ではありません(´・ω・`)