[백준(JAVA)] 9017번: 크로스 컨트리

문제

✔ 난이도 - Silver 3

설명

• 우선 팀 들어온순서 입력받아서 저장해 -> teamSequence

  • 팀 별 인원수 hashmap에 저장해 (팀, 인원수)
  • 만약 6명 미달이면 미달인팀 리스트에 저장해. -> underSix

• teamSequence 다시 보면서 6명 이상인팀만 등수매겨

  • 이 때 팀 별로
    - 4명 합산 점수
    - 5등 점수
    - 현재 각 팀 별 몇 명 저장했는지
    관리해야함. 이후 다중정렬때문에 HashMap 사용함.

• 4명 합산 점수가 가장 작은 팀이 우승이고 만약 동점이면 5등 점수가 가장 작은 팀이 이김.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0){
            int N = Integer.parseInt(br.readLine());

            int[] teamSequence = new int[N];
            Map<Integer, Integer> hm = new HashMap<>();

            int sequence = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()){
                int team = Integer.parseInt(st.nextToken());
                teamSequence[sequence++] = team;
                hm.put(team, hm.getOrDefault(team, 0) + 1);
            }
            
            HashSet<Integer> underSix = new HashSet<>();

            Iterator<Map.Entry<Integer, Integer>> itr = hm.entrySet().iterator();
            while (itr.hasNext()){
                Map.Entry<Integer, Integer> entry = itr.next();
                if (entry.getValue() < 6) underSix.add(entry.getKey());
            }

            // 등수 매기기

            Map<Integer, Integer> fourSum = new HashMap<>();
            Map<Integer, Integer> fifth = new HashMap<>();
            Map<Integer, Integer> memberCount = new HashMap<>();

            int score = 1;
            for (int i = 0; i < N; i++){
                int team = teamSequence[i];

                if (underSix.contains(team)) continue;

                int memCount = memberCount.getOrDefault(team, 0) + 1;
                memberCount.put(team, memCount);

                if (memCount <= 4) fourSum.put(team, fourSum.getOrDefault(team, 0) + score);
                else if (memCount == 5) fifth.put(team, score);

                score++;
            }

            ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(fourSum.entrySet());
            list.sort((a,b) -> {
                if (!a.getValue().equals(b.getValue())){
                    return a.getValue().compareTo(b.getValue());
                }

                return fifth.get(a.getKey()).compareTo(fifth.get(b.getKey()));
            });

            sb.append(list.get(0).getKey()).append('\n');          
        }

        System.out.println(sb);
    }
}

⏰ 시간복잡도

$O(N \log N)$

• 데이터 읽기 및 필터링: $O(N)$
• 팀별 점수 합산: $O(N)$
• 팀 정렬: $O(M \log M)$

따라서 이 알고리즘의 최종 복잡도는 $O(N + M \log M)$인데, $M$은 결국 $N$에 종속된 값이니까 대세에 지장 없이 (전체적인 결과나 큰 흐름에는 별 영향을 주지 않으니) $O(N \log N)$
혹은 $N$이 워낙 작아서 $O(N)$에 가깝다고 봐도 무방한 수준

정렬이 들어갔으니 $\log$가 붙는 게 맞고, 정렬 대상이 팀($M$)이라서 실제로는 $N \log N$보다도 훨씬 빠르게 돌아간다!

만약 $M$과 $N$이 서로 아무 상관이 없는 독립적인 값이라면(예: 정점 $V$개와 간선 $E$개인 그래프 문제), 그때는 $O(V+E)$처럼 따로 써줘야 함. 하지만 지금처럼 $M$이 $N$의 일부분($M \le N$)일 때는 $N$으로 바꿔 써도 무방하다!