[백준 19640: JAVA] 화장실의 규칙

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

19640번: 화장실의 규칙

---

[1회차] 11월 13일, 킹받는다고 추천받은 문제 

문제 접근 방법 (사용 자료구조, 알고리즘)

 

입력
(1) 사원 N명, 회장이 지시한 줄 수 M, 데카 앞에 있는 사원 수 K
(2) Employee 객체( 사원번호, 근무일수, 화장실 급한 정도, 서 있는 열) 생성해서  객체 배열을 만들어 준다.
   객체 배열은 Line[M][N%M == 0? N/M : N/M + 1] 로 선언한다. 만약, 사원의 수가 줄의 개수보다 작다면 (N < M) 이면 M을 N으로 설정한다.
(3) 사원 정보들을 입력받으면서 즉시 배열에 넣어준다. N명까지만 받아야 하므로 N명이 넘어가면 반복문을 종료하고 입력을 받으면서 max int 배열에 각 줄에 서 있는 사람들의 수를 넣어준다 

로직 화장실 보내기
(0) 맨 처음 문제에서 요구한 정렬 조건을 설정한 우선순위 큐를 생성해서 각 줄의 선두주자를 넣어준다. 그리고 탐색할 줄의 탐색 인덱스를 저장하는 배열을 하나 수행했다.
(1) 데카의 차례가 올 때까지 반복문을 수행한다.
(2) 우선순위 큐에서 한 명씩 poll 하고 만약 poll한 사원의 no 가 K + 1(데카의 사원번호) 와 같다면 종료하고 그렇지 않으면 poll한 사원이 속해져 있는 줄의 그 다음 사람을 넣어준다. 인덱스 저장 배열에도 해당 줄의 인덱스를 하나 늘려준다.

 

 

메모리 & 시간

TMI인데 나 이거 JAVA 전체 1등함 하하

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K, size, ans, max[];
	static Employee[][] line;
	
	static class Employee{
		int no, days, hard, row;

		public Employee(int no, int days, int hard, int row) {
			this.no = no;
			this.days = days;
			this.hard = hard;
			this.row = row;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		size = N % M == 0? N / M : N / M + 1;
		M = N < M? N : M;
		line = new Employee[size][M];
		max = new int[M];
		
		int idx = 0;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < M; j++) {
				if(++idx == N + 1) break;
				st = new StringTokenizer(in.readLine());
				line[i][j] = new Employee(idx, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), j);
				max[j] += 1;
			}
		}
		
		goRestroom();
		System.out.println(ans);
	}
	
	private static void goRestroom() {
		int idx[] = new int[M];
		PriorityQueue<Employee> head = new PriorityQueue<>(new Comparator<Employee>() {
			@Override
			public int compare(Employee o1, Employee o2) {
				if(o1.days == o2.days) {
					if(o1.hard == o2.hard) {
						return o1.row - o2.row;
					}
					return o2.hard - o1.hard;
				}
				return o2.days - o1.days;
			}
		});
		
		for (int i = 0; i < M; i++) {
			head.add(line[idx[i]][i]);
		}
		
		while(true) {
			// 화장실 보내자~~
			Employee header = head.poll();
			
			if(header.no == K + 1) {
				break;
			}
			
			idx[header.row] += 1;
			if(idx[header.row] < max[header.row]) head.add(line[idx[header.row]][header.row]);
			
			ans++;
			
		}
	}
}

 

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
10분	15분	30분