질문 요약

• 질문문제 : ALLERGY
• 사용언어 : java
• 온라인 저지 결과 에러메시지
  • RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded)
• 제출답안 URL : https://algospot.com/judge/submission/detail/246365

해결 과정 요약

1. 원본 데이터 할당
2. 원본 데이터 읽기
3. 원본 데이터 사용 위한 변수 할당
4. 최소음식수 찾기 위한 모든 경우의 수 목록 생성(Combination)
5. 경우의 수 리스트 기반으로 모두가 음식 먹을 수 있는지 검증
6. 경우의 수 리스트의 최소크기 리스트부터 검증을 시작하며, 조건 만족시 해당 리스트의 크기만 반환
7. 전체 케이스 만큼 다시 반복

• 할당 과정 : 주어진 데이터를 String 에 전부 할당
  • String input = "2\n4 6\ncl bom dara minzy\n2 dara minzy\n2 cl minzy\n2 cl .....";
• 원본데이터 읽기
  • Scanner 클래스 사용
• 다음과 같은 차례로 데이터 읽고 ArrayList형 변수에 저장하기 (아래 정보를 저장하는 변수는 전부 클래스 변수로 선언)
  1. 총케이스 수
  2. 사람 수, 음식 수
  3. 사람 이름
  4. 음식을 만들 수 있는 사람 목록 (사람 이름과 매칭 되는 값을 숫자로 대입)
• 조합(Combination) 리스트 생성
  1. 음식별 먹을 수 있는 정보의 조합리스트 생성(이하 가능조합리스트)
  2. 크기가 3일 경우, 크기가 1을 제외한 가능조합리스트는 크기 3까지 만든다. ex) (1,2), (1,3), (2,3), (1,2,3)
• 모두가 음식 먹을 수 있는 지 검증
  • 위의 가능조합리스트의 순번에 해당하는 음식을 전부 체크한 뒤, 모두가 음식을 먹을 수 있는지 검증

• 검증 알고리즘

  • 가능조합리스트의 음식별 가능 인덱스를 전부 임시리스트 변수에 add
  • contain을 사용하여 포함되어 있다면 add 안함
  • 임시리스트의 크기가 사람 수와 같다면 가능조합리스트의 크기를 리턴

• 추측해결방법

  • 입력데이터를 메모리에 한번에 저장하지 말고 하나 입력 받고 소멸시켜야 될 것으로 생각되나 어디까지나 추측