[Baekjoon] 14184_IOI 2017 Logo

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

---

< IOI 2017 Logo >

 

문제 풀이 

 

투표 1차, 2차, 3차, 총합을 구한 후 

1) 총합 내림차순

2) 1차 내림차순

3) 2차 내림차순

으로 정렬하여 우승 로고를 구한다.

 

* 우승 로고가 여러 개라면 ID기준 오름차순으로 정렬한다.

 

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.Comparator;
 import java.util.HashMap;
 import java.util.StringTokenizer;
 
 public class _14184_ { // IOI 2017 Logo
 
 	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;
 
 		int n = 0;
 
 		while ((n = Integer.parseInt(bf.readLine())) != 0) {
 			HashMap<Integer, int[]> map = new HashMap<>();
 
 			for (int i = 0; i < n; i++) {
 				st = new StringTokenizer(bf.readLine());
 				int d = Integer.parseInt(st.nextToken());
 
 				for (int j = 0; j < d; j++) {
 					int id = Integer.parseInt(st.nextToken());
 
 					if (map.containsKey(id)) {
 						map.get(id)[j] += (3 - j);
 						map.get(id)[3] += (3 - j);
 					} else {
 						int[] arr = new int[4];
 						arr[j] += (3 - j);
 						arr[3] += (3 - j);
 						map.put(id, arr);
 					}
 				}
 			}
 			ArrayList<Integer> list = new ArrayList<>(map.keySet());
 			Collections.sort(list, new Comparator<Integer>() {
 				@Override
 				public int compare(Integer o1, Integer o2) {
 					if (map.get(o2)[3] == map.get(o1)[3]) {
 						if (map.get(o2)[0] == map.get(o1)[0]) {
 							return map.get(o2)[1] - map.get(o1)[1];
 						}
 						return map.get(o2)[0] - map.get(o1)[0];
 					}
 					return map.get(o2)[3] - map.get(o1)[3];
 				}
 			});
 
 			ArrayList<Integer> result = new ArrayList<>();
 			result.add(list.get(0));
 
 			for (int i = 1; i < list.size(); i++) {
 				if (map.get(list.get(0))[3] == map.get(list.get(i))[3]
 						&& map.get(list.get(0))[0] == map.get(list.get(i))[0]
 						&& map.get(list.get(0))[1] == map.get(list.get(i))[1]) {
 					result.add(list.get(i));
 				} else {
 					break;
 				}
 			}
 
 			Collections.sort(result);
 			for (int i = 0; i < result.size(); i++) {
 				bw.write(result.get(i) + " ");
 			}
 			bw.write("\n");
 		}
 		bw.flush();
 	}
 }

변수)
n : 투표자 수
map : HashMap <ID, 투표 값>
d : 투표자가 선택한 로고 수
id : 투표자가 선택한 로고
list : HashMap key -> ArrayList
result : 우승 로고

 

투표자 수 n이 0이 아닐 때까지 다음 과정을 반복한다.

 

1) n만큼 투표자가 선택한 로고 수와 투표자가 선택한 로고를 입력받는다.

2) 투표자가 선택한 로고를 1차, 2차, 3차에 맞게 점수를 더한다.

3) HashMap의 key 값을 ArrayList로 변환한다.

4) ArrayList를 총합 내림차순, 1차 내림차순, 2차 내림차순으로 정렬한다.

5) 우승 로고를 구한다. 이때, 4번에서 말한 기준값이 모두 같다면 여러 로고가 우승이므로 ArrayList에 추가한다.

6) ArrayList를 오름차순으로 정렬 후 출력한다.

---

---