[백준(JAVA)] 20006번: 랭킹전 대기열

세하·2026년 4월 3일

Java 백준

[백준] 문제풀이

목록 보기

93/94

문제

✔ 난이도 - Silver 2

설명

각 방 별 기준 점수 기록 필요 -> 처음으로 방 들어온 사람(생성한 사람)
새로운사람 들어올때마다 방 돌면서 빈자리있고, 기준 점수에서 -+10인지 보고 맞으면 넣고, 아니면 방 새로 만들기

방1 (기준레벨, 인원수)

레벨 / 닉넴
레벨 / 닉넴
...

방2 (기준레벨, 인원수)

레벨 / 닉넴
레벨 / 닉넴
...

방과 멤버를 class로 빼기 -> Room, Player

풀이

public class Main {

    static class Player implements Comparable<Player> {
        int level;
        String nickname;

        Player(int level, String nickname) {
            this.level = level;
            this.nickname = nickname;
        }

        @Override
        public int compareTo(Player o){
            return this.nickname.compareTo(o.nickname);
        }
    }

    static class Room {
        int baseLevel;
        int compacity;
        ArrayList<Player> players = new ArrayList<>();

        Room(int baseLevel, String nickname, int compacity){
            this.baseLevel = baseLevel;
            this.compacity = compacity;
            players.add(new Player(baseLevel, nickname));
        }

        void join(int level, String nickname) {
            players.add(new Player(level, nickname));
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        ArrayList<Room> rooms = new ArrayList<>();

        for (int i = 0; i < p; i++){
            st = new StringTokenizer(br.readLine());
            int level = Integer.parseInt(st.nextToken());
            String nickname = st.nextToken();

            boolean joinRoom = false;
            for(Room room : rooms){
                if (room.players.size() < m && Math.abs(room.baseLevel - level) <= 10) {
                    room.join(level, nickname);
                    joinRoom = true;
                    break;
                }
            }

            if (!joinRoom){
                rooms.add(new Room(level, nickname, m));
            }
        }

        for (Room room : rooms){
            if (room.players.size() == m) sb.append("Started!\n");
            else sb.append("Waiting!\n");

            Collections.sort(room.players);

            for (Player player : room.players){
                sb.append(player.level).append(" ").append(player.nickname).append("\n");
            }
        }
        
        System.out.println(sb);
    }
}

⏰ 시간복잡도

O(N^2)

플레이어 수 $P$ , 방 인원수 $M$ 일 때 플레이어마다 방 목록을 순회하므로 방 개수는 최대 $P$ 개, 즉 $O(P^2)$
마지막 정렬 부분은 각 방의 정렬 $O(M \log M)$ 이 방 개수만큼 반복

💡 TIL

Comparable, @Override compareTo

자바는 기준 이 뭔지를 궁금해한다.
ArrayList<Integer>를 정렬할 때는 자바가 고민을 안함 -> 1보다 2가 크다는 걸 이미 알고 있으니까!

근데 위에서 직접 만든 Player 객체는 어떤걸 기준으로 정렬해야할지 모른다.
이걸 알려주는게 Comparable 인터페이스

compareTo -> 정렬 규칙 만들기

Comparable을 구현(implements)한다는 건, 객체 안에 '나랑 쟤랑 비교하면 누가 앞이야?' 라는 규칙(compareTo 메서드)을 심어놓는 것
(재정의하는 것이므로 @Override를 붙여준다.)

@Override
public int compareTo(Player o) {
    // 내가 쟤보다 앞이면 음수(-1)
    // 똑같으면 0
    // 내가 쟤보다 뒤면 양수(1)를 반환해라
    return this.nickname.compareTo(o.nickname); 
}