[백준] 1713.후보 추천하기 / 시뮬레이션

@시뮬레이션 / 2h

푸는건 30분도 안걸렸는데 최댓값 설정 잘못해서 그거 찾느라 한참 걸렸다ㅜㅜ

 

 

문제 링크

https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

 

구현 포인트

맵을 두개 사용했다.

countMap : <학생 번호, 추천받은 횟수>

idxMap : <학생 번호, 게시한 시점>

 

if (countMap.containsKey) { // 이미 추천 받은 학생이라면

        추천 횟수 + 1을 해준다

} else { //새로 추천 받은 학생이라면

         if (countMap.size >= N) { //이미 사진틀이 다 차있다면

                  for문으로 countMap을 돌면서 최솟값(가장 적은 추천수)을 찾는다

                  for문으로 idxMap을 돌면서 그 최소값을 가진 학생들 중 게시 시점이 가장 빠른 학생을 찾는다

                  해당 학생을 countMap과 idxMap에서 모두 삭제한다

         }

         새로 추천 받은 학생을 countMap과 idxMap에 넣어준다

}

 

 

삽질 포인트

총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

여기서 학생이 사진틀에 게시된 시점은 최대 1000일 수 있는데, 학생 번호와 착각해서 최댓값을 100으로 줬다가

계속 틀려서 잡느라 너무 힘들었다 ㅜㅜ

 

오늘의 교훈

최댓값은 Integer.MAX_VALUE를 활용하자!

 

 

코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
		Map<Integer, Integer> idxMap = new HashMap<Integer, Integer>();		
		
		int N = Integer.parseInt(br.readLine());
		int size = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < size; i++) {
			int temp = Integer.parseInt(st.nextToken());
			
			if (countMap.containsKey(temp)) {
				countMap.put(temp, countMap.get(temp) + 1);
			} else {
				if (countMap.size() >= N) {
					int minVal = Integer.MAX_VALUE;
					int minIdx = Integer.MAX_VALUE;
					int minIdxKey = 0;
					for (Integer key : countMap.keySet()) {
						if (minVal > countMap.get(key)) {
							minVal = countMap.get(key);
							minIdxKey = key;
						}
					}

					for (Integer idxKey : idxMap.keySet()) {
						if (minVal == countMap.get(idxKey)) {
							if (minIdx > idxMap.get(idxKey)) {
								minIdx = idxMap.get(idxKey);
								minIdxKey = idxKey;
							}
						}
					}
					countMap.remove(minIdxKey);
					idxMap.remove(minIdxKey);
				}
				countMap.put(temp, 1);
				idxMap.put(temp, i);
			}
		}
		
		List<Integer> list = new ArrayList<>(countMap.keySet());
		Collections.sort(list);
		for (Integer key : list)
			sb.append(key + " ");
		System.out.println(sb);
	}
}

ㅎㅎ.. 별것도 아니었는데 진짜..힘들었다..ㅎㅎㅎ

끝!