백준 23349번 졸업 사진 S1 - Hash

 

 

구간중에 가장 사람이 많이 겹치는곳을 찾고,
그 구간이 여러 장소에서 겹친다면 알파뱃 순으로 정렬.

정해진 장소에서 여러 시간대가 사람이 많다면 가장 빠른 시간대로 출력한다.

>> 이 규칙들을 제대로 안읽고 모든 구간에서 가장 긴 구간 찾고,,, 세그먼트 나누고 2시간은 걸린거 같다.

막상 다 작성하니까 가장 빠른이라 훨씬 쉽게 해결됐다...

 

해시 + 정렬 쓖쓖..

해시맵에 배열을 넣어서 구간 범위를 증가시켜 주었고, MAX 값을 가진 장소를 리스트에 넣어서 구간을 체크해주었다.

 

import java.io.*;
import java.util.*;
 
public class Main { // Boj_23349_졸업 사진
    static class PlaceTime implements Comparable<PlaceTime> {
        String place;
        int start;
 
        PlaceTime(String place, int start) {
            this.place = place;
            this.start = start;
        }
 
        @Override
        public int compareTo(PlaceTime o) {
            if (!this.place.equals(o.place)) {
                return this.place.compareTo(o.place); // 알파뱃 정렬
            }
            return Integer.compare(this.start, o.start); // 가장 빠른 시간
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        Map<String, int[]> map = new HashMap<>();
        Set<String> nameSet = new HashSet<>();
        int max = -1;
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String place = st.nextToken();
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
 
            if (nameSet.contains(name)) continue;
            nameSet.add(name);
            int[] counts = map.computeIfAbsent(place, k -> new int[50001]);
            for (int idx = start; idx < end; idx++) {
                counts[idx]++;
                max = Math.max(max, counts[idx]);
            }
        }
 
        List<PlaceTime> haveMax_List = new ArrayList<>();
        for (String place : map.keySet()) {
            int[] counts = map.get(place);
            for (int i = 0; i < counts.length; i++) {
                if (counts[i] == max) {
                    haveMax_List.add(new PlaceTime(place, i));
                    break;
                }
            }
        }
 
        Collections.sort(haveMax_List);
        PlaceTime now_Place = haveMax_List.get(0);
        int end = (findEnd(map.get(now_Place.place), now_Place.start, max));
        System.out.println(now_Place.place + " " + now_Place.start + " " + end);
    }
 
    private static int findEnd(int[] counts, int start, int max) {
        int end = start;
        while (end < counts.length && counts[end] == max) {
            end++;
        }
        return end;
    }
}