ALLERGY 오류 질문드립니다.

  • kasia
    kasia

    ALLERGY 문제 질문드립니다.

    ALLERGY가 있는 친구들이 먹을 수 있는 음식수의 최소 갯수를 구하는 문제입니다.

    1. 이차원 배열로 먹을 수 있는 음식수를 정의한다.

      peopleCnt = sc.nextInt();
      foodCnt = sc.nextInt();
      foods = new boolean[foodCnt][peopleCnt];
      eats = new int[foodCnt];
      friends = new String[peopleCnt];
      makeFoods(sc);

      private static void makeFoods(Scanner sc) {
      for (int i = 0; i < peopleCnt; i++) {
      friends[i] = sc.next();
      }
      for (int i = 0; i < foodCnt; i++) {
      eats[i] = sc.nextInt();
      for (int j = 0; j < eats[i]; j++) {
      int pos = findFriendPos(sc.next());
      foods[i][pos] = true;
      }
      }
      }

    2. 각 음식마다 모든 친구들이 먹을수 있는 최소 음식 수를 구한다.

      • 이때 순서는 가장 많은 친구들에게 제공하는 음식 기준입니다.

      int min = 0;
      for (int j = 0; j < foodCnt; j++) {
      if (j == 0) {
      min = changeTrue(j);
      } else {
      min = Math.min(min, changeTrue(j));
      }
      }

      private static int changeTrue(int index) {
      boolean[] sol = foods[index].clone();
      int addIndex = -1;
      int addCnt = 1;
      // sol 배열이 모두 true가 될때까지 구합니다.
      while (true) {
      int changeCnt;
      int max = 0;
      for (int i = 0; i < foodCnt; i++) {
      if (i == index) continue;
      changeCnt = 0;
      for (int j = 0; j < foods[i].length; j++) {
      if (sol[j]) continue;
      // 이미 true인 것을 제외하고 해당 음식이 true이면 횟수 증가
      if (foods[i][j]) {
      changeCnt++;
      }

      }
      int m = Math.max(changeCnt, max);
      // true가장 많이 바뀐것을 구함
      if (m != max) {

      addIndex = i;
                  max = m;
              }
          }
          // 모두 true이면 Loop 중지
          if (max == 0)break;
      
          if (addIndex >= 0) {
              // true가장 많이 바뀐 음식을 비교하여 true로 변경
              sol = addTrue(sol,addIndex);
              addCnt++;
          }
      }
      
      // 음식 횟수 리턴
      return addCnt;

      }

    3. 비교하여 최소 음식수를 구한다.

      System.out.println(String.valueOf(min));

    전체 코드
    public class Main {
    //ALLERGY

    private static boolean[][] foods;
    private static int[] eats;
    private static int peopleCnt;
    private static int foodCnt;
    private static String[] friends;
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            peopleCnt = sc.nextInt();
            foodCnt = sc.nextInt();
            foods = new boolean[foodCnt][peopleCnt];
            eats = new int[foodCnt];
            friends = new String[peopleCnt];
            makeFoods(sc);
            int min = 0;
            for (int j = 0; j < foodCnt; j++) {
                if (j == 0) {
                    min = changeTrue(j);
                } else {
                    min = Math.min(min, changeTrue(j));
                }
            }
            System.out.println(String.valueOf(min));
        }
    }
    
    private static void makeFoods(Scanner sc) {
        for (int i = 0; i < peopleCnt; i++) {
            friends[i] = sc.next();
        }
        for (int i = 0; i < foodCnt; i++) {
            eats[i] = sc.nextInt();
            for (int j = 0; j < eats[i]; j++) {
                int pos = findFriendPos(sc.next());
                foods[i][pos] = true;
            }
        }
    }
    
    private static int changeTrue(int index) {
        boolean[] sol = foods[index].clone();
        int addIndex = -1;
        int addCnt = 1;
        while (true) {
            int changeCnt;
            int max = 0;
            for (int i = 0; i < foodCnt; i++) {
                if (i == index) continue;
                changeCnt = 0;
                for (int j = 0; j < foods[i].length; j++) {
                    if (sol[j]) continue;
                    if (foods[i][j]) {
                        changeCnt++;
                    }
                }
                int m = Math.max(changeCnt, max);
                if (m != max) {
                    addIndex = i;
                    max = m;
                }
            }
            if (max == 0)break;
            if (addIndex >= 0) {
                sol = addTrue(sol,addIndex);
                addCnt++;
            }
        }
        return addCnt;
    }   
    
    private static boolean[] addTrue(boolean[] sol, int index){
        for (int i = 0; i < foods[index].length; i++) {
            if(sol[i]) continue;
            if(foods[index][i]) sol[i]=true;    
        }
        return sol;
    }
    
    private static int findFriendPos(String friendName) {
        int result = -1;
        for (int i = 0; i < peopleCnt; i++) {
            if (friends[i].equals(friendName)) {
                result = i;
                break;
            }
        }
        return result;
    }

    }

    위 코드로 제출시 에러가 발생하는데 이유를 모르겠습니다.
    고수분들의 조언 부탁드립니다.


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