[백준/Java] 11972번 Contaminated Milk

-Code

import java.io.*;
import java.util.*;

public class BOJ11972 {
    static class DrinkInfo {
        int milkNum, drinkTime;

        public DrinkInfo(int milkNum, int drinkTime) {
            this.milkNum = milkNum;
            this.drinkTime = drinkTime;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int friendCnt = Integer.parseInt(st.nextToken());
        int milkCnt = Integer.parseInt(st.nextToken());
        int drinkCnt = Integer.parseInt(st.nextToken());
        int sickCnt = Integer.parseInt(st.nextToken());

        Map<Integer, ArrayList<DrinkInfo>> friends = new HashMap<>();
        for (int i = 0; i < drinkCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int personNum = Integer.parseInt(st.nextToken());
            int milkNum = Integer.parseInt(st.nextToken());
            int drinkTime = Integer.parseInt(st.nextToken());
            
            ArrayList<DrinkInfo> info = friends.getOrDefault(personNum, new ArrayList<>());
            info.add(new DrinkInfo(milkNum, drinkTime));
            friends.put(personNum, info);
        }


        boolean[] isSickPossible = new boolean[milkCnt + 1];
        Arrays.fill(isSickPossible, true);
        for (int i = 0; i < sickCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int personNum = Integer.parseInt(st.nextToken());
            int drinkTime = Integer.parseInt(st.nextToken());

            // 그 사람의 먹은 기록이 있는 경우 검사
            List<DrinkInfo> history = friends.get(personNum);
            Set<Integer> drinkSet = new HashSet<>();
            if (history != null) {
                // 아픈 시간 이전의 모든 우유 번호 저장
                for (DrinkInfo info : history) {
                    if (info.drinkTime < drinkTime) {
                        drinkSet.add(info.milkNum);
                    }
                }
            }
            // 아픈 사람의 우유에 포함 되지 않으면 false
            for (int m = 1; m <= milkCnt; m++) {
                if (!drinkSet.contains(m)) {
                    isSickPossible[m] = false;
                }
            }
        }
        // 필요한 약 갯수 구하기
        int needMedicineCnt = 0;
        for (int m = 1; m <= milkCnt; m++) {
            if (isSickPossible[m]) {
                int cnt = 0;
                for (int p = 1; p <= friendCnt; p++) {
                    // 먹은 우유가 없으면 넘어감
                    if (friends.get(p) == null) continue;
                    // 먹은 우유 중 해당 우유가 있으면 갯수 추가
                    for (DrinkInfo info : friends.get(p)) {
                        if (info.milkNum == m) {
                            cnt++;
                            break;
                        }
                    }
                }
                needMedicineCnt = Math.max(needMedicineCnt, cnt);
            }
        }
        System.out.println(needMedicineCnt);
        br.close();
    }
}

처음에는 아픈 사람이 나오면 그 사람에 대한 우유를 먹은 시간이 아픈 시간보다 빠른 모든 우유의 시간을 저장하고 그걸 이용해 문제를 풀려했습니다.

그렇게 되면 범위가 너무 커져서 검사 값이 오염되어 이상하게 풀리게 되어 문제가 생겼고 좀 찾아보니 아픈 시간 이전에 먹은 우유를 기록하고 그게 아닌 우유를 모두 제외하는 방식과 그 결과를 모든 우유에 대해 검사하라는 힌트를 얻었습니다.

이를 통해 로직을 수정후 다시 모든 사람을 조사해 각각 우유를 다 검사하고 그 값 중 가장 큰 값을 출력하는 식으로 해서 해결하여 문제의 제약 조건을 활용해 후보군을 얼마나 정교하게 필터해야하는 것을 다시 깨달았습니다.