백준 8979번 올림픽 S5 - 정렬

 

ㅋㅋ ㅋ ㅋㅋㅋㅋ 아 초등부였냐고

 

오늘은 가볍게 풀자면서 골랐던 문제다.. 난이도가 뭐라고 기세등등하게 키보드를 두둘겼다가 한참 혼났다.

쉬운것도 제대로하자 실수하지말자.. 쫌

자자 점수표이올시다.

서브태스크로 문제 배점을 공개한 문제인데...

디버깅 한참 걸렸다.

 

아직 정렬개념이 확실하게 안잡힌게 분명하다... 보단 사사로운 문제에 시간을 썼다.

순위 이놈 때문에 1시간반을 넘게 썼다. 정리해보자..

 

문제 조건이 주루루 있다.

1. 금메달 수가 더 많은 나라 
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 

음~ 이해하기 쉽다.

금메달이 가치가 높아(1등만 기억하는 세상) 금메달이 많다면 국가 등수가 올라간다.

단. 동일하다면 <- 이게 문제다.

 

예제처럼 이렇게 주어진다면.

• 1위 -> 1번 국가
• 2위 -> 3,4번 국가
• 4위 -> 3번 국가 

가 된다.

 

금메달 은메달 동메달 순으로 Comparator를 오버라이드해서 정렬하고, 순위 로직만 넣어주면 되겠다.

금메달 개수를 배열로 받았고,

Arrays.sort(arr, new Comparator<int[]>() { // 금은동 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return o2[1] - o1[1];
                } else if (o1[2] != o2[2]) {
                    return o2[2] - o1[2];
                } else {
                    return o2[3] - o1[3];
                }
            }
        });

o1,o2로 나눠서 비교해 주었다.

 

순위는 1과 2가 같아서 1위가 2명이라면, 그 다음으로 오는친구나 2위가 아닌 3위를 줘야했다.

따라서 rank와 cnt 변수를 주어서 로직을 짜줬다.

만약 다 동일하지 않다면 rank에 cnt를 더해 일반적인 순위 로직을 적용 시켰고, 아니라면 단순 등수만 올려줬다.

for (int i = 0; i < N; i++) {
            if (i > 0 && (arr[i][1] != arr[i-1][1] || 
            arr[i][2] != arr[i-1][2] || arr[i][3] != arr[i-1][3])) {
                rank += cnt;
                cnt = 1;
            } else if (i > 0) {
                cnt++;
            }

 

왜 여기서 시간을 그리 뺏겼는지 원..

같은 등수가 생기는 상황에서 cnt를 초기화를 안해서 값에 오류가 있었다.. 

 

12점 코드

int cnt = 1;
        int rank = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i + 1][1] != arr[i][1] || arr[i + 1][2] != arr[i][2] || arr[i + 1][3] != arr[i][3]) {
                rank += cnt; // 겹치지 않는다면
            } else {// 동일하다면
                cnt++;
            }
//            System.out.println(arr[i][0] + "번의 등수 :" + rank);
            if (arr[i][0] == K) {
                System.out.println(rank);
                break;
            }
        }

 

 

100점 코드 

import java.io.*;
import java.util.*;
 
class Node {
    int now, dist;
    Node(int now, int dist) {
        this.now = now;
        this.dist = dist;
    }
}
 
public class Main {
    static List<List<Node>> tree;
    static boolean[] visit;
    static int N;
    static int max;
    static int far_Node;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
 
        tree = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            tree.add(new ArrayList<>());
        }
 
        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            tree.get(start).add(new Node(end, weight));
            tree.get(end).add(new Node(start, weight));
        }
        // 가장 먼 노드 찾기.
        visit = new boolean[N + 1];
        dfs(1, 0);
        
        visit = new boolean[N + 1];
        dfs(far_Node, 0);
 
        System.out.println(max);
    }
 
    public static void dfs(int node, int value) {
        visit[node] = true;
 
        if (value > max) { // 합이 더 크다면 멀다고 판단.
            max = value;
            far_Node = node;
        }
 
        for (Node next : tree.get(node)) {
            if (!visit[next.now]) {
                dfs(next.now, value + next.dist);
            }
        }
    }
}