[Algorithm/Java] 백준 20006번 - 랭킹전 대기열 (작성중)
https://www.acmicpc.net/problem/20006
🔍 문제 풀이
문제 도식화
List<List<User>> rooms
rooms.get(0)→ 첫 번째 방
rooms.get(1) → 두 번째 방
rooms.get(2) → 세 번째 방 …
이렇게 방에 접근할 수 있.
그리고 그 방의 처음 들어간 사람은 항상 get(0)이 된다.
즉, 두 번째 방에 처음 들어간 사람은
User firstInSecondRoom = rooms.get(1).get(0);
System.out.println(firstInSecondRoom.level + " " + firstInSecondRoom.name);
이렇게 꺼내면 된다.
정리
rooms.get(방인덱스) → 해당 방 전체 리스트
rooms.get(방인덱스).get(0) → 그 방의 첫 번째(=기준) 유저
// 첫 번째 방 기준 레벨
int base1 = rooms.get(0).get(0).level;
// 두 번째 방 기준 레벨
int base2 = rooms.get(1).get(0).level;
💻 코드
[방법 1] 일중리스트
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// input
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int p = Integer.parseInt(st.nextToken()); // 플레이어 수
int m = Integer.parseInt(st.nextToken()); // 방의 정원
Player[] players = new Player[p];
// 정보 저장
for (int i = 0; i < p; i++) {
st = new StringTokenizer(br.readLine());
int level = Integer.parseInt(st.nextToken()); // 레벨
String name = st.nextToken(); // 닉네임
players[i] = new Player(level, name);
}
for (int i = 0; i < p; i++) {
ArrayList<Player> room = new ArrayList<>();
if (!players[i].check) {
for (int j = i; j < p; j++) {
if (room.size() == m) break;
int level = players[j].level;
String name = players[j].name;
if (!players[j].check && players[i].level - 10 <= level && level <= players[i].level + 10 ) {
players[j].check = true;
room.add(new Player(level, name));
}
}
Collections.sort(room, (a,b) -> a.name.compareTo(b.name));
if (room.size() == m) sb.append("Started!").append("\n");
else sb.append("Waiting!").append("\n");
for (Player player : room) {
sb.append(player.level).append(" ").append(player.name).append("\n");
}
}
}
System.out.println(sb);
}
static class Player {
int level;
String name;
boolean check;
public Player(int level, String name) {
this.level = level;
this.name = name;
}
}
}
[방법 2] 이중 리스트
rooms가 처음엔 비어 있으니까, 첫 번째 유저를 처리할 때는 안쪽 for(List<User> room : rooms)가 아예 실행되지 않음
따라서 첫 번쨰 유저부터 방 생성
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// input
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken()); // 플레이어 수
int m = Integer.parseInt(st.nextToken()); // 방의 정원
// 정보 저장
List<User> users = new ArrayList<>();
for (int i = 0; i < p; i++) {
st = new StringTokenizer(br.readLine());
int level = Integer.parseInt(st.nextToken()); // 레벨
String name = st.nextToken(); // 닉네임
users.add(new User(level, name));
}
// 방들을 리스트로 관리 (리스트 안에 리스트)
List<List<User>> rooms = new ArrayList<>(); // 방 하나씩 순회
for(User user:users){
boolean joined = false;
for(List<User> room : rooms) {
if(room.size() < m) {
int baseLevel = room.get(0).level; // 그 방 안에서 0번쨰로 들어온 유저
if(baseLevel - 10 <= user.level && user.level <= baseLevel + 10){
room.add(user);
joined = true;
break;
}
}
}
if(!joined) {
List<User> newRoom = new ArrayList<>();
newRoom.add(user);
rooms.add(newRoom);
}
}
// 출력
StringBuilder sb = new StringBuilder();
for(List<User> room : rooms) {
if(room.size() == m) sb.append("Started!\n");
else sb.append("Waiting!\n");
Collections.sort(room, (a, b) -> a.name.compareTo(b.name));
for (User u : room) {
sb.append(u.level).append(" ").append(u.name).append("\n");
}
}
System.out.print(sb);
}
static class User {
int level;
String name;
public User(int level, String name) {
this.level = level;
this.name = name;
}
}
}
[방법 3] 클래스
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// input
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken()); // 플레이어 수
int m = Integer.parseInt(st.nextToken()); // 방의 정원
// 정보 저장
List<User> userList = new ArrayList<>();
for(int i=0; i<p; i++){
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken()); // 레벨
String n = st.nextToken(); // 닉네임
userList.add(new User(l, n));
}
List<Room> rooms = new ArrayList<>();
// solve
for(User user:userList) {
boolean joined = false;
// 기존 방 탐색 (레벨 범위, 정원 미만)
for (Room room : rooms) {
if (room.users.size() < m &&
user.level >= room.level - 10 &&
user.level <= room.level + 10) {
room.users.add(user);
joined = true;
break;
}
}
// 못 들어가면 새 방 생성
if (!joined) {
Room newRoom = new Room(user.level);
newRoom.users.add(user);
rooms.add(newRoom);
}
}
// 방 생성 순서대로 출력
StringBuilder sb = new StringBuilder();
for (Room room : rooms) {
if (room.users.size() == m) sb.append("Started!\n");
else sb.append("Waiting!\n");
room.users.sort((a, b) -> a.name.compareTo(b.name));
for (User u : room.users) {
sb.append(u.level).append(" ").append(u.name).append("\n");
}
}
System.out.print(sb);
}
public static class User {
int level;
String name;
public User(int level, String name) {
this.level = level;
this.name = name;
}
}
public static class Room {
int level;
ArrayList<User> users = new ArrayList<>();
Room(int level) {
this.level = level;
}
}
}
댓글남기기