Allergy 문제... 특별한 케이스좀 알려주세요 ㅠㅠ

  • ycyc02
    ycyc02

    알러지 문제에서 왠만한 답들은 맞는것 같은데
    오답이라고 하니까
    어떤경우에 오답인지 도저히 생각이 안납니다 ㅠㅠ..
    어떤경우에 오답이 생기는지 worstCase 에대해서
    알려주시면 감사하겠습니다,,,,

    import java.util.Scanner;
    
    
    public class Allergy {
    
        static int[] marker;
        static int[] selectedIndex;
        static int[][] Matrix;
        static int minimum;
        static int Min = Integer.MAX_VALUE;
        static int[] test;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Friend f;
            int testCase = sc.nextInt();
            for (int i = 0; i < testCase; i++) {
                int numOfFriends = sc.nextInt();// 친구수 입력받음
                int numOfFoods = sc.nextInt();// 음식수 입력 받음
                f = new Friend(numOfFriends);
                Matrix = new int[numOfFoods][numOfFriends];
                // 즉 1행에 음식1 이있고 그거에대한 사람 o x 그런 마커가 있겟지 그런식으로 만듬.
                for (int j = 0; j < numOfFriends; j++) {
                    f.addFriends(sc.next());
                }// 사람입력받음
    
                for (int j = 0; j < numOfFoods; j++) {// 음식에 관한 정보들을 입력받아야되
                    int l = sc.nextInt();
                    for (int k = 0; k < l; k++) {
                        String temp = sc.next();
                        int temp1 = f.rindex(temp);
                        Matrix[j][temp1] = 1;// 이로써 맵핑을 시켯다.
                    }
    
                }
                minimum = 0;// 최솟값저장을 위한
                marker = new int[numOfFriends];
                selectedIndex = new int[numOfFoods];
    
                while(true){
                    for (int j = 0; j < numOfFoods; j++) {
                        if (isPossible(j)) {
                            Mapping(j,marker);
    
                            compare(j);
                        }
    
                    }
    
                    break;
                }
                System.out.println(minimum);
    
            }
    
        }// main함수의 끝 end of main
    
        public static boolean check() {
            for (int i = 0; i < marker.length; i++) {
                if (marker[i] != 1) {
                    return false;
                }
            }
            return true;
        }
    
        public static void compare(int k) {
            for (int i =0;true;i++) {
                if(i>minimum-1){
                    break;
                }
                test = new int[Matrix[0].length];
                boolean x = true;
                for(int r = 0 ; r <minimum;r++){
                    if(r==i){
                        continue;
                    }else{
                        Mapping(selectedIndex[r], test);
                    }
                }
                Mapping(k,test);
    
                for(int j = 0 ; j < test.length; j ++){
                    if(test[j]!=marker[j]){
    
                        x=false;
                        break;
                    }
                }
                if(x){
                    System.arraycopy(selectedIndex, 0, selectedIndex, 0, i);
                    System.arraycopy(selectedIndex, i+1, selectedIndex,i , minimum-(i+1));
                    minimum--;
                    i--;
    
                }
    
            }
            test = new int[Matrix[0].length];
            for(int i = 0 ; i < minimum; i ++){
            Mapping(selectedIndex[i], test);
            }
            boolean check = false;
            for(int i = 0 ; i < test.length;i++){
                if(marker[i]==1&&test[i]!=1){
                    check= true;
                }
            }
    
            if(check){
            selectedIndex[minimum] = k;
            minimum++;
            }
        }
    
        public static void Mapping(int k,int[] target) {
            for (int i = 0; i < marker.length; i++) {
                if (Matrix[k][i] == 1) {
                    target[i] = 1;
                }
            }
    
        }
    
        public static boolean isPossible(int k) {// matrix의 행.
            //현재 선택된 행의 값들이 selectedIndex안에 있는 값들중에 혹시 포함되는게 있으면.
            //false로 가면되지..
            for (int i = 0; i < minimum; i++) {
                if(isAinB(k, i)){
                    return false;
                }
    
    
            }
            return true;
    
        }
        public static boolean isAinB(int a,int b){
            //a와 b둘다 행이야.
            //a가 b안에 들있으면 true;
            for(int i=0;i< Matrix[0].length;i++){
                if(Matrix[a][i]==1&&Matrix[b][i]!=1){
                    return false;
                }
    
            }
            return true;
        }
    
        public static class Friend {
            String[] FriendsList;
            int count;
    
            public Friend(int num) {
                FriendsList = new String[num];
                count = 0;
            }
    
            public void addFriends(String a) {
                FriendsList[count] = a;
                count++;
            }
    
            public int rindex(String a) {
                int k = -1;
                for (int i = 0; i < FriendsList.length; i++) {
                    if (FriendsList[i].equals(a)) {
                        k = i;
                        break;
                    }
                }
                return k;
    
            }
        }
    }
    

    8년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.