풀이 방법
이번 문제는 너무 생각을 많이 해서 오히려 빙빙 돌아서 접근한 문제였다.
브루트포스로 돌려버려도 시간초과가 나지 않기에
어떤 자료구조를 사용해서 효율적인 처리를 할 것인가를 생각하면 될 문제였다.
처음에는 List를 사용하기로 결정했다.
등수에 따라 점수가 부여되는 방식이기에, 6명을 이루지 못하는 팀만 찾아서 없애준다면 인덱스를 이용해 점수를 부여하면 되지않을까 라고 생각했었다.
하지만, 이 접근은 매우 효율적이지 못했다.
List에서 원하는 값(여기선 팀)을 가진 요소만 삭제해주기 어려웠다.- 만약 6명이 안되는 팀을 제외한
List를 구했다고 하더라도, 각 팀별로 5번째 사람을 찾기에 더러운? 연산이 필요하다.
1번을 우선 해결해볼까 해서 list의 removeAll 메서드를 찾아봤었는데, ArrayList.removeAll(Collection<?> c) 이처럼 인자를 Collection 형식으로 받아서 적합하지 않았다. (내가 원한건 원하는 값을 가진 요소를 모두 없애는 기능이였는데..)
결국 여러 관련 블로그를 찾아보다가 Map을 활용해서 해결한 풀이를 다수 발견했다.
나도 Map을 고민해보긴 했지만, 중복이 불가능하다는 점과 관련 메서드를 많이 모르기 때문에 제외했던 . 것같다.
여기서 사용한 주요 메서드는 getOrDefault(Object key, V DefaultValue) 메서드이다.
만약 인자로 들어간 key값이 존재한다면, value값을 반환해주고
key값이 존재하지 않거나 null이라면, default로 설정한 값으로 반환해준다.
이걸 어떻게 활용했을까??
teams.put(team, teams.getOrDefault(team,0)+1);이런식으로 Map에 team에 member가 추가될 때 마다 1을 증가시켜줘서 최종적으론 팀의 구성원 수를 구할 수 있었다.
또한 이를 통해 1~4번째 member들의 score 총 합과, 5번째 들어온 member의 socre 또한 쉽게 구할 수 있었다.
최종 1등을 구하기 위한 정렬은 List로 변환한 뒤 람다 함수를 사용하는 방법인데,
Map의 value 값을 서로 비교할때 객체 참조 주소를 사용하여 비교하기에 ==을 사용하면 구분하지 못한다는 것을 주의하자.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
Map<Integer, Integer> teams = new HashMap<>(); // 6명의 팀을 이루는지 체크할 맵
int[] rank = new int[n]; // 들어온 순서를 기록할 배열
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<n;j++) {
int team = Integer.parseInt(st.nextToken());
teams.put(team, teams.getOrDefault(team,0)+1);
rank[j] = team;
}
Map<Integer,Integer> scoreMap = new HashMap<>();
Map<Integer,Integer> tempMap = new HashMap<>();
int[] fifthMember = new int[n+1];
int score = 1;
for(int team : rank) {
if(teams.get(team) < 6) // 팀을 구성하지 못했다면 제외
continue;
tempMap.put(team, tempMap.getOrDefault(team, 0)+1);
if(tempMap.get(team) <= 4) { // 4등까지는 점수 계산
scoreMap.put(team, scoreMap.getOrDefault(team, 0)+score);
}
else if(tempMap.get(team) == 5){ // 비슷할때 비교할 5등 점수 저장
fifthMember[team] = score;
}
score++;
}
// 순위를 비교하기위한 정렬
List<Integer> sorted = new ArrayList<>(scoreMap.keySet());
sorted.sort((o1, o2) -> {
if(Objects.equals(scoreMap.get(o1), scoreMap.get(o2)))
return fifthMember[o1] - fifthMember[o2];
else
return scoreMap.get(o1) - scoreMap.get(o2);
});
sb.append(sorted.get(0)).append("\n");
}
System.out.println(sb);
}
}
