[ 백준 / BOJ 5766 ] 할아버지는 유명해!

https://www.acmicpc.net/problem/5766

5766번: 할아버지는 유명해!

 

문제

---

"그 뉴스" 를 보고 온 가족이 들떴습니다. 모두들 할아버지께서 수 십년간 굉장히 실력있는  브릿지(카드게임의 일종) 선수였다는 것은 알고 있었지만, 할아버지가 역대 최고의 bridge 선수로서 기네스북에 오른다는 소식은 정말이지 놀라웠죠!

IBA(국제 브릿지 협회)는 수 년간, 매주 가장 실력있는 선수들의 랭킹 정보를 기록해왔습니다.  매주 랭킹에 선수의 이름이 오를 때마다 선수의 포인트가 1포인트씩 오르는데, 할아버지께서 가장 많은 포인트를 얻어서 최고의 브릿지 선수로 선정되었습니다.

할아버지께는 그와 브릿지 순위를 경쟁하는 친구들이 많이 있었기 때문에, 할아버지는 어떤 선수(들)가 2등을 했는지 정말 궁금하셨습니다.  

IBA 랭킹 정보는 이제 온라인에 올라와 있고, 할아버지께서 당신에게 도움을 요청했습니다. 당신은 매주마다의 랭킹 정보 리스트를 인풋으로 받아 2등 선수가 누구인지 알아내는 프로그램을 짜야 합니다.

입력

---

각 선수는 1~10000까지의 정수(선수 번호)로 식별됩니다. 인풋은 여러 테스트 케이스들로 구성됩니다.

테스트 케이스의 첫 행에는 두 정수 N과 M이 주어지는데, 다음 행부터 N(2<=N<=500)주 동안의 매주 상위 M(2<=M<=500)명의 랭킹 정보가 주어짐을 의미합니다.

그 다음 N행의 인풋이 주어지는데 각 행은 한 주의 랭킹 정보입니다. 각 행은 공백으로 구분되는 M개의 정수들이 주어집니다.  

• 각 테스트 케이스에는 최고점의 선수가 단 한 명만 존재합니다.
• 매주마다의 랭킹 정보에는 서로 다른 M개의 선수 번호가 주어집니다.

N과 M이 모두 0으로 주어지는 행이 인풋의 마지막입니다.

출력

---

각 테스트 케이스마다,  당신의 프로그램은 한 행에 2등인 선수(들)의 번호를 출력해야 합니다. 2등인 선수가 두 명 이상인 경우(동점자 발생), 각 선수 번호를 공백으로 구분하여 오름차순으로 출력해야 합니다.

풀이

---

처음에 배열로하면 시간초과 날 것이라고 생각해서,,,,,  Map으로 풀었는데....... 🤷‍♀️ 시간초과‼️‼️‼️

 

그래서 객체 배열로 해보니... 정답‼️🤦‍♀️

 

코드

---

Map으로 시간초과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder sb = new StringBuilder();

        int N, M;
        while(true){
            TreeMap<Integer, Integer> player = new TreeMap<>();
            stringTokenizer = new StringTokenizer(br.readLine());
            N = Integer.parseInt(stringTokenizer.nextToken());
            M = Integer.parseInt(stringTokenizer.nextToken());

            if(N == 0 && M == 0)
                break;

            for(int i = 0 ; i < N ; i++){
                stringTokenizer = new StringTokenizer(br.readLine());
                for(int j = 0 ; j < M ; j++){
                    int playerNum = Integer.parseInt(stringTokenizer.nextToken());
                    player.put(playerNum, player.getOrDefault(playerNum, 0)+1);
                }
            }
            
            List<Integer> listKeySet = new ArrayList<>(player.keySet());
            Collections.sort(listKeySet, (value1, value2) -> (player.get(value2).compareTo(player.get(value1))));

            int secondPlayer = player.get(listKeySet.get(1));
            sb.append(listKeySet.get(1)).append(" ");
            for(int i = 2 ; i < listKeySet.size() ; i++){
                if(secondPlayer == player.get(listKeySet.get(i)))
                    sb.append(listKeySet.get(i)).append(" ");
                else{
                    sb.append('\n');
                    break;
                }
            }
        }
        System.out.println(sb);
    }
}

객체 배열로 맞은 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main_BOJ_5766_할아버지는유명해 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder sb = new StringBuilder();

        while(true){
            stringTokenizer = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());

            if(N == 0 && M == 0)
                break;

            player players[] = new player[10001];
            for(int i = 0 ; i < 10001 ; i++){
                players[i] = new player(i, 0);
            }

            for(int i = 0 ; i < N ; i++){
                stringTokenizer = new StringTokenizer(br.readLine());
                for(int j= 0 ; j < M ; j++){
                    int playerNum = Integer.parseInt(stringTokenizer.nextToken());
                    players[playerNum].score++;
                }
            }

            Arrays.sort(players);

            int second = players[1].score;
            for(int i = 1; i < 10001 ; i++){
                if(players[i].score == second){
                    sb.append(players[i].num).append(" ");
                }
            }
          sb.append("\n");
        }

        System.out.println(sb);
    } 

    public static class player implements Comparable<player>{
        int num;
        int score;

        player(int num, int score){
            this.num = num;
            this.score = score;
        }

        @Override
        public int compareTo(player o) {
            // TODO Auto-generated method stub
            int result = o.score - this.score;

            if(result == 0)
                result = this.num - o.num;

            return result;
        }
    }
}