[Baekjoon] 21208_Gratitude

문제(출처: https://www.acmicpc.net/problem/21208)

---

< Gratitude >

 

문제 풀이 

 

HashMap을 사용하여 각 item의 빈도수와 등장 순서를 저장한다. item 빈도수 내림차순, 등장 순서 내림차순으로 정렬하여 K개를 출력한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class _21208_ { // Gratitude
	static class Info implements Comparable<Info> {
		private String item;
		private int num;
		private int recent;
        
		public Info(int num, int recent) {
			this.num = num;
			this.recent = recent;
		}
        
		@Override
		public int compareTo(Info o) {
			if (this.num == o.num) {
				return o.recent - this.recent;
			}
			return o.num - this.num;
		}
	}
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
        
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
        
		HashMap<String, Info> map = new HashMap<>();
		for (int i = 0; i < 3 * n; i++) {
			String str = bf.readLine();
			if (map.containsKey(str)) {
				Info info = map.get(str);
				info.num += 1;
				info.recent = i;
			} else {
				map.put(str, new Info(1, i));
			}
		}
        
		ArrayList<Info> list = new ArrayList<>();
        
		for (String str : map.keySet()) {
			Info info = map.get(str);
			info.item = str;
			list.add(info);
		}
		Collections.sort(list);
        
		for (int i = 0; i < k; i++) {
			if (i >= list.size()) {
				break;
			}
			bw.write(list.get(i).item + "\n");
		}
		bw.flush();
	}
}

변수)
n, k : day, 출력 개수
map : HashMap
list : Info를 저장하는 ArrayList

 

Info

item, num, recent를 변수로 가지며 num 내림차순, recent 내림차순으로 정렬한다.

 

Main

n, k를 입력받는다. 3xn만큼 item을 입력받으며 map에 존재한다면 num과 recent를 업데이트, map에 존재하지 않다면 값을 추가한다. map을 전체 탐색하면서 ArrayList에 Info 객체를 저장한 후 정렬한다. 최종 ArrayList의 k개를 출력한다.

---

---