📌 Problem
N x N 크기의 교실이 있다. 1 x 1 칸마다 한 명의 학생이 앉을 수 있다. N x N명의 학생들이 순서대로 등교한다. 먼저 등교한순서대로 자신이 앉고 싶은 자리에 앉을 수 있다. 학생마다 선호하는 친구들이 4명씩 있다. 다음과 같은 방법으로 자리를 구한다.
-
주변(동서남북)에 선호하는 학생이 가장 많은 자리에 앉는다.
-
1번 조건이 동일한 경우에는 주변에 빈자리가 가장 많은 자리에 앉는다.
-
2번 조건이 동일한 경우에는 더 앞 자리(Row 0)에 앉는다.
-
3번 조건이 동일한 경우에는 창가(Col 0)에 가까운 자리에 앉는다.
📌 Solution
1번과 2번 조건은 각 빈자리를 탐색하면서 계산할 수 있다. 이 때 (0, 0) 자리부터 (N-1, N-1) 자리 순서로 탐색을 하면 3번과 4번 조건도 자연스럽게 충족할 수 있다.
ArrangeDTO arrange = new ArrangeDTO(-1, -1, -1, -1);
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
if (students[i][j] == null) arrange = arrange.max(ifArrangeAt(i, j, preferSnos));
students[arrange.getArrangeI()][arrange.getArrangeJ()] = new Student(sno, preferSnos);ArrangeDTO는 특정 자리에 앉았을 때 주변 선호 학생의 수와 빈 자리의 수를 가지는 데이터 클래스이다. ifArrageAt를 통해 이를 계산할 수 있으며 ArrangeDTO.max()를 통해 1, 2번 조건을 충족하는 ArrangeDTO를 얻을 수 있다.
최종적인 자리 배치도에서 각 학생별 만족도 또한 완전 탐색을 통해서 계산할 수 있다
public int calculateTotalPreference() {
int satisfactionScore = 0;
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
satisfactionScore += students[i][j].calculateSatisfaction(i, j, students);
return satisfactionScore;
}📌 Code
int N = Integer.parseInt(reader.readLine());
ClassRoom classRoom = new ClassRoom(N);
int studentNum = N * N;
while (studentNum-- > 0) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int sno = Integer.parseInt(tokenizer.nextToken());
Set<Integer> preferSnos = new HashSet<>() {{
while (tokenizer.hasMoreTokens()) add(Integer.parseInt(tokenizer.nextToken()));
}};
// 자리 배치
classRoom.arrangeStudent(sno, preferSnos);
}
result.append(classRoom.calculateTotalPreference());class ClassRoom {
private final Student[][] students; // 각 자리별 배치된 학생(null 은 빈자리)
private final int SIZE;
public ClassRoom(int size) {
students = new Student[size][size];
SIZE = size;
}
/**
* 등교한 학생이 원하는 자리에 앉는다.
* @param sno 등교한 학생의 번호
* @param preferSnos 등교한 학생이 선호하는 친구들의 번호
*/
public void arrangeStudent(int sno, Set<Integer> preferSnos) {
// 학생이 앉고자하는 자리에 대한 정보
ArrangeDTO arrange = new ArrangeDTO(-1, -1, -1, -1);
// 자리 완전 탐색
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
// 빈 자리의 자리 정보 계산 및 비교
if (students[i][j] == null) arrange = arrange.max(ifArrangeAt(i, j, preferSnos));
// 조건에 만족하는 자리에 앉기
students[arrange.getArrangeI()][arrange.getArrangeJ()] = new Student(sno, preferSnos);
}
/**
* 현재 자리에 앉았을 때의 자리 정보를 계산한다.
* @param locI 현재 자리의 row
* @param locJ 현재 자리의 column
* @param preferSnos 학생이 선호하는 학생들의 번호
* @return 자리 정보(주변 선호 학생 수, 주변 빈 자리 수, 위치)
*/
private ArrangeDTO ifArrangeAt(int locI, int locJ, Set<Integer> preferSnos) {
int preferCount = 0, blankCount = 0;
// 주변 자리들을 확인하면서 선호하는 학생의 수와 빈 자리의 수 확인
for (Adjacent adjacent : Adjacent.values()) {
try {
Student friend = students[locI + adjacent.row][locJ + adjacent.col];
if (friend == null) blankCount++; // 빈 자리
else if (friend.isPreferred(preferSnos)) preferCount++; // 선호하는 학생
} catch (ArrayIndexOutOfBoundsException ignore) {
}
}
return new ArrangeDTO(preferCount, blankCount, locI, locJ);
}
/**
* 자리 배치 완료 후 모든 학생들의 만족도 합산 값으로 계산한다.
* @return 전체 학생 만족도
*/
public int calculateTotalPreference() {
int satisfactionScore = 0;
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
satisfactionScore += students[i][j].calculateSatisfaction(i, j, students);
return satisfactionScore;
}
}
class Student {
private final int SNO; // 학생 번호
private final Set<Integer> preferSnos; // 선호하는 학생들의 번호
public Student(int SNO, Set<Integer> preferSnos) {
this.SNO = SNO;
this.preferSnos = preferSnos;
}
/**
* 현재 학생이 다른 학생이 선호하는 학생인지 확인한다.
* @param preferSnos 다른 학생의 선호 학생 목록
* @return 현재 학생에 대한 다른 학생의 선호 여부
*/
public boolean isPreferred(Set<Integer> preferSnos) {
return preferSnos.contains(SNO);
}
/**
* 앉은 자리에 대한 만족도를 계산한다.
* @param locI 앉은 자리의 row
* @param locJ 앉은 자리의 column
* @param students 자리 배치도
* @return 학생의 만족도
*/
public int calculateSatisfaction(int locI, int locJ, Student[][] students) {
int numberOfPreferredFriend = 0; // 주변에 위치한 선호 학생의 수
for (Adjacent adjacent : Adjacent.values()) {
try {
Student student = students[locI + adjacent.row][locJ + adjacent.col];
if (student.isPreferred(preferSnos)) numberOfPreferredFriend++;
} catch (ArrayIndexOutOfBoundsException ignore) {
}
}
return calculateSatisfaction(numberOfPreferredFriend);
}
/**
* 주변 선호 학생 수를 바탕으로 만족도 점수 계산
* @param numberOfPreferredFriend 주변 선호 학생 수
* @return 만족도 점수
*/
private int calculateSatisfaction(int numberOfPreferredFriend) {
switch (numberOfPreferredFriend) {
case 1:
return 1;
case 2:
return 10;
case 3:
return 100;
case 4:
return 1000;
default:
return 0;
}
}
}
class ArrangeDTO {
private final int numberOfPreferredFriend; // 주변 선호 학생 수
private final int numberOfEmptySeat; // 주변 빈 자리 수
private final int arrangeI, arrangeJ; // 위치
public ArrangeDTO(int numberOfPreferredFriend, int numberOfEmptySeat, int arrangeI, int arrangeJ) {
this.numberOfPreferredFriend = numberOfPreferredFriend;
this.numberOfEmptySeat = numberOfEmptySeat;
this.arrangeI = arrangeI;
this.arrangeJ = arrangeJ;
}
/**
* 두 데이터를 비교하여 조건에 더 적합한 데이터 반환
* @param compareTo 비교하고자하는 데이터
* @return 조건에 적합한 데이터
*/
public ArrangeDTO max(ArrangeDTO compareTo) {
// 조건 1
if (numberOfPreferredFriend < compareTo.numberOfPreferredFriend) return compareTo;
// 조건 2
else if (numberOfPreferredFriend == compareTo.numberOfPreferredFriend
&& numberOfEmptySeat < compareTo.numberOfEmptySeat) return compareTo;
// 조건 3, 4
return this;
}
public int getArrangeI() {
return arrangeI;
}
public int getArrangeJ() {
return arrangeJ;
}
}
enum Adjacent {
NORTH(-1, 0),
EAST(0, 1),
SOUTH(1, 0),
WEST(0, -1);
final int row, col;
Adjacent(int row, int col) {
this.row = row;
this.col = col;
}
public int row() {
return row;
}
public int col() {
return col;
}
}
Hello, Devs!