Java 백준 20006 랭킹전 대기열

백준 링크

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

20006번: 랭킹전 대기열

---

문제

입력

출력

입출력 예시

 

---

제출한 코드

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	static int p, m;
	static List<List<String[]>> data = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		init();
	}

	public static void init() throws Exception {
		st = new StringTokenizer(br.readLine());
		p = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		for (int i = 0; i < p; i++) {
			st = new StringTokenizer(br.readLine());
			// level, name
			int l = Integer.parseInt(st.nextToken());
			String n = st.nextToken();
			// 입력을 받으면서 바로 방에 배치
			run(l, n);
		}
		for (int i = 0; i < data.size(); i++) {
			checkRoom(i);
		}
		System.out.println(sb);
	}

	public static void run(int level, String name) {
		// 현재 존재하는 방 개수
		int size = data.size();

		// 방이 1개라도 존재한다면
		if (size != 0) {
			// 방 순회
			for (int i = 0; i < size; i++) {
				// 현재 방의 범위 = 맨 처음 방에 추가된 사람의 level
				int nowRange = Integer.parseInt(data.get(i).get(0)[0]);
				
				// +-10 범위와 방 정원 확인
				if (nowRange - 10 <= level && nowRange + 10 >= level && data.get(i).size() < m) {
					data.get(i).add(new String[] { Integer.toString(level), name });
					return;
				}
			}
		}
		// 방 리스트 맨 마지막에 새롭게 생성
		data.add(new ArrayList<>());
		int addIdx = data.size();
		data.get(addIdx - 1).add(new String[] { Integer.toString(level), name });
	}

	public static void checkRoom(int idx) {
		// 조회해야하는 전체 방 개수
		int nowRoomSize = data.get(idx).size();
		
		// 정렬 기준을 level이 아닌 name 기준으로 정렬
		Collections.sort(data.get(idx), new Comparator<String[]>() {
			public int compare(String[] o1, String[] o2) {
				return o1[1].compareTo(o2[1]);
			};
		});

		// 방 상태 확인
		if (nowRoomSize == m) {
			sb.append("Started!\n");
		} else {
			sb.append("Waiting!\n");
		}
		
		// StringBuilder에 추가
		for (String[] output : data.get(idx)) {
			sb.append(output[0]).append(" ").append(output[1]).append("\n");

		}

	}
}

 

 

방과 사람의 정보를 저장하는 자료구조를 고민한다고 시간이 걸린 문제였다.

 

1. List -> List -> String[] 구조로 데이터를 저장한다.

( 방 ( 동적으로 늘어나야함 ) -> 인원 ( 입력값에 따라 달라짐 ) -> 사람 정보 ( 0번 = level, 1번 = name ) )

2. 처음 입력을 받을 때 level은 사람이 들어갈 방을 찾기전이라 Integer타입으로 로직 안에서 핸들링한다.

3. 새로운 사람이 들어올 때 마다 전체 방을 순회한다.

4. 입장 가능한 방이 있는 경우 제일 마지막에 추가한다.

( 데이터를 넣으면서 정렬을 하게 된다면 방 level로 쓰이고 있던 0번 index의 위치가 변동되기 때문이다. )

5. 입력이 종료되었다면 for each문으로 전체 방을 순회하면서 정렬 및 출력을 한다.

( String[0] = level, String[1] = name 으로 저장 되었기에 새롭게 compare를 정의해주고 사용한다. )