백준 23349번 졸업 사진 자바

문제 링크

금융권 코딩 테스트를 준비하면서 풀게된 자료구조를 활용한 구현 문제이다

문제

올해 졸업식에 참가하는 모든 사람은 비행기가 보이게 사진을 찍고싶어하지만, 졸업식은 하루뿐이라 모든 사람이 원하는 장소와 시간에 촬영할 수 없다.

따라서 학교에서는 최대한 많은 사람이 촬영할 수 있도록 미리 졸업식 전날 원하는 장소와 시간대를 제출받아 예상되는 혼잡 장소와 시간대를 공지하기로 하였다.

제출은 다음과 같은 값을 가진다.

• 학생 이름(name): 제출한 학생의 이름이다. 공백을 포함하지 않는 영어 소문자로 구성된 10자 이하의 한 단어로 구성된다. 만약 한 학생이 여러 번 제출한 경우, 가장 첫 번째 제출 이외의 제출들은 모두 무시한다.
• 장소(place): 학생이 촬영하기를 원하는 장소이다. 공백을 포함하지 않는 영어 소문자로 구성된 20자 이하의 한 단어로 구성된다.
• 시간대(time): 학생이 촬영하기를 원하는 시간대이다. 공백으로 구분된 두 개의 시각으로 주어지며, 시각은 $50,000$ 이하의 양의 정수로 주어진다. 첫 번째 시각은 촬영 시작 시각, 두 번째 시각은 촬영 종료 시각을 나타낸다. 단, 종료 시각이 시작 시각보다 항상 크다.

제출된 장소와 시간대의 목록을 이용해 학교가 혼잡 장소와 시간대를 공지하는 방법은 다음과 같다.

1. 가장 많은 사람이 제출한 (장소, 시간대) 쌍을 선택한다.
2. 만약 $1$번에 해당하는 구간이 여러 개라면, 사전 순으로 가장 앞에 오는 장소를 선택한다. 사전 순의 기준은 아스키 코드 순이다. 예를 들어 구간 배열 ['ab', 'a', 'aa', ba']를 정렬한 배열은 ['a', 'aa', 'ab', 'ba']가 된다.
3. 만약 $2$번에서 고른 장소에 가장 많이 제출된 시간대가 여러 개라면, 가장 빠른 시간대를 고른다.

문제 풀이

1. 학생 이름은 첫 제출 이외의 제출은 모두 무시하기 때문에 Set을 사용한다
2. 장소와 시간대를 HashMap을 활용한다
3. 장소별 방문 시간을 기록하기 위해 TreeMap을 써서 그 시간대 방문자 수를 넣는다
   3-1. 각 장소에서 방문자가 가장 많았던 시간을 추적하기 위해 최대 방문자 수 갱신
4. 방문자 가장 많았던 시간을 찾고 해당 시간을 기준으로 시간대의 끝 (end)를 찾는다

• HashMap<String, TreeMap<Integer, Integer>>
  장소별 시간별 방문자 수 저장
• HashMap
  중복된 학생을 무시하기 위해 사용
• List
  방문자가 많았던 시간대를 저장하고 알파벳 순 및 시간순 정렬

코드

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

/**
 * HashMap HashSet TreeMap을 이용한 자료구조 구현 문제
 * 
 * 1. 학생 이름, 장소 시작시간, 종료시간 으로 방문데이터 기록
 * 중복된 학생은 처리 하지 않기 위해 hashset 사용
 * 2. 장소를 key로 하는 HashMap
 * 각 장소별 방문 시간 기록하기 위해 시간별 방문자 카운트하는 TreeMap 사용
 * Treemap으로 방문자 수 자동 정렬
 * 
 * 가장 많았던 시간 추척하기위해 max 갱신
 * 방문자 가장 많았던 시간 장소 찾고 시작 끝 찾기
 * 
 */

public class Main {	
	
	static int N;
	
	static class PlaceTime implements Comparable<PlaceTime> {
		String place;
		int start;
		
		public PlaceTime(String place, int start) {
			this.place = place;
			this.start = start;
		}
		
		@Override
		public int compareTo(PlaceTime pt) {
			if(!this.place.equals(pt.place)) {
				return this.place.compareTo(pt.place);
			}
			return Integer.compare(this.start,  pt.start);
		}
	}

	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		HashMap<String, TreeMap<Integer, Integer>> map = new HashMap<>();
		Set<String> set = 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(set.contains(name))
				continue;
			set.add(name);

			
			TreeMap<Integer, Integer> timeSlots = map.computeIfAbsent(place, k -> new TreeMap<>());
			for(int time = start; time < end; time++) {
				timeSlots.put(time, timeSlots.getOrDefault(time, 0) + 1);
				max = Math.max(max,  timeSlots.get(time));
			}
		}
		
		List<PlaceTime> maxVisitPlaces = new ArrayList<>();
		for(String place : map.keySet()) {
			TreeMap<Integer, Integer> timeSlots = map.get(place);
			for(Map.Entry<Integer, Integer> timeEntry : timeSlots.entrySet()) {
				int time = timeEntry.getKey();
				if(timeEntry.getValue() == max) {
					maxVisitPlaces.add(new PlaceTime(place, time));
					break;
				}
			}
		}
		
		Collections.sort(maxVisitPlaces);
		
		PlaceTime bestTime = maxVisitPlaces.get(0);
		int endTime = findEnd(map.get(bestTime.place), bestTime.start, max);
		bw.write(bestTime.place + " " + bestTime.start + " " + endTime);
		bw.flush();
		bw.close();
		
	
	}
	static int findEnd(TreeMap<Integer, Integer> timeSlots, int start, int max) {
        int end = start;
        while (timeSlots.containsKey(end) && timeSlots.get(end) == max) {
            end++;
        }
        return end;
    }

}