[랜덤 마라톤] 졸업 사진(23349)

1. 문제 풀이 아이디어

• 다양한 자료구조를 활용해 필요한 정보를 저장하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        Set<String> names = new HashSet<>();
        Map<String, int[]> map = new HashMap<>();
        PriorityQueue<String> places = new PriorityQueue<>();
        int max = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            String name = stringTokenizer.nextToken();
            if (names.contains(name)) {
                continue;
            }
            names.add(name);
            String place = stringTokenizer.nextToken();
            int start = Integer.parseInt(stringTokenizer.nextToken());
            int end = Integer.parseInt(stringTokenizer.nextToken());
            int[] time;
            if (map.containsKey(place)) {
                time = map.get(place);
            } else {
                time = new int[50001];
                map.put(place, time);
            }
            int curMax = 0;
            for (int j = start; j < end; j++) {
                time[j]++;
                curMax = Math.max(curMax, time[j]);
            }
            if (curMax > max) {
                max = curMax;
                places.clear();
                places.add(place);
            } else if (curMax == max) {
                places.add(place);
            }
        }
        String place = places.poll();
        int[] time = map.get(place);
        int start = 0;
        int end = 0;
        for (int i = 1; i < 50001; i++) {
            if (start == 0) {
                if (time[i] == max) {
                    start = i;
                }
            } else {
                if (time[i] != max) {
                    end = i;
                    break;
                }
            }
        }
        System.out.println(place + " " + start + " " + end);
        bufferedReader.close();
    }
}

3. 정리

• 중복을 방지하기 위해 학생의 이름을 저장할 names 집합을 정의한다.

• 장소와 시간을 저장하기 위해 map을 정의한다.

• 최대한 많은 사람이 촬영할 수 있는 장소를 저장하기 위해 places를 사용하며, 사전순으로 정렬되도록 PriorityQueue로 정의한다.

• 입력을 받을 때 names를 활용해 이미 입력된 학생은 제외한다.

• map에 해당 장소가 이미 존재하면 기존 값을 가져와 사용하고, 존재하지 않으면 새로운 배을 생성해 추가한다.

• 이 장소의 최대 촬영자 수를 저장할 curMax를 0으로 초기화한 뒤, start부터 end까지 값을 증가시키며 최대 촬영자 수를 갱신한다.

• 현재 장소의 최대 촬영자 수가 전체 최대 촬영자 수보다 많으면 최대값을 갱신하고 places를 초기화한 후 현재 장소를 추가한다.

• 최대 촬영자 수가 동일하다면 현재 장소만 추가한다.

• 모든 입력 처리가 끝난 후 places에서 가장 앞에 있는 장소를 가져오고, map에서 해당 장소의 최대 촬영자 수와 일치하는 시간의 시작과 끝을 찾아 출력한다.