백준 21608 상어 초등학교 - 삼성 SW 역량 테스트 기출

백준 21608 상어 초등학교 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

21608번: 상어 초등학교

 

2. 문제 해결에 대한 아이디어

1. 학생들을 배치하고나서, 인접한 학생들 중 선호하는 학생이 얼마나 있는지에 따라 만족도에 대한 점수를 매긴다.

2. 만족도에 대한 점수를 매길 때, 어떤 학생의 선호학생 리스트를 사용해야한다.

3. 따라서, Student 클래스의 리스트를 만들어 각 객체마다 번호와 선호학생 리스트를 저장해두었다.

4. 번호로 접근할 수 있도록, 번호를 기준으로 오름차순으로 정렬했다.

5. 인접한 학생이 선호 학생인지의 여부는 ArrayList.cotains(); 를 사용했다.

6. 자리 선택의 조건은 아래와 같다.

   . 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 정한다.

   . 그 중, 인접한 칸에서 비어있는 칸이 가장 많은 칸으로 정한다.

   . 그 중, 행의 번호가 가장 작은 칸으로 정한다.

   . 그 중, 열의 번호가 가장 작은 칸으로 정한다.

7. candidate와 secondCandidate는 각 단계별로 자리 후보의 위치를 저장해두었다.

8. 행과 열 번호에 대한 조건은 secondCandidate에 가장 작은 행, 열부터 저장되므로 따로 신경 쓸 필요 없었다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static class Student implements Comparable<Student> {
		int no;
		ArrayList<Integer> like;

		public Student(int no, ArrayList<Integer> like) {
			super();
			this.no = no;
			this.like = like;
		}

		@Override
		public int compareTo(Student o) {

			return this.no - o.no;
		}

	}

	static class Pair {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static ArrayList<Student> students = new ArrayList<Student>();
	static int N;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int[][] board;
	static int score = 0;

	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\상어초등학교_21608\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] n = br.readLine().split(" ");
		N = Integer.parseInt(n[0]);
		board = new int[N][N];

		for (int i = 0; i < N * N; i++) {
			String[] line = br.readLine().split(" ");
			int key = Integer.parseInt(line[0]);
			ArrayList<Integer> temp = new ArrayList<>();
			for (int j = 1; j < 5; j++) {
				temp.add(Integer.parseInt(line[j]));
			}
			students.add(new Student(key, temp));
		}

		for (int i = 0; i < students.size(); i++) {
			selectSeat(students.get(i));
		}

		Collections.sort(students);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int index = board[i][j] - 1;
				ArrayList<Integer> values = students.get(index).like;
				int cnt = 0;
				for (int d = 0; d < 4; d++) {
					int ii = i + dirY[d];
					int jj = j + dirX[d];

					if (ii >= N || jj >= N || ii < 0 || jj < 0 || board[ii][jj] == 0)
						continue;
					if (values.contains(board[ii][jj]))
						cnt++;
				}
				switch (cnt) {
				case 0:
					score += 0;
					break;
				case 1:
					score += 1;
					break;
				case 2:
					score += 10;
					break;
				case 3:
					score += 100;
					break;
				case 4:
					score += 1000;
					break;
				}
			}
		}
		System.out.println(score);

	}

	public static void selectSeat(Student now) {
		int no = now.no;
		ArrayList<Integer> like = now.like;
		ArrayList<Pair> candidate = new ArrayList<>();
		int likeCnt = 0;

		// 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 0) {
					int cnt = 0;
					for (int d = 0; d < 4; d++) {
						int ii = i + dirY[d];
						int jj = j + dirX[d];

						if (ii >= N || jj >= N || ii < 0 || jj < 0 || board[ii][jj] == 0)
							continue;

						if (like.contains(board[ii][jj]))
							++cnt;
					}
					if (likeCnt < cnt) {
						candidate.clear();
						candidate.add(new Pair(i, j));
						likeCnt = cnt;
					} else if (likeCnt == cnt) {
						candidate.add(new Pair(i, j));
					}
				}
			}
		}
		if (candidate.size() == 1) {
			Pair p = candidate.get(0);
			board[p.y][p.x] = no;
			return;
		}

		// 2. 1을 만족하는 칸이 여러개이면 인접한 칸 중에서 비어이있는 칸이 가장 많은 칸으로 자리를 정한다.
		int secondCnt = 0;
		ArrayList<Pair> secondCandidate = new ArrayList<>();
		for (int i = 0; i < candidate.size(); i++) {
			Pair p = candidate.get(i);
			int cnt = 0;
			for (int d = 0; d < 4; d++) {
				int yy = p.y + dirY[d];
				int xx = p.x + dirX[d];

				if (yy >= N || xx >= N || yy < 0 || xx < 0 || board[yy][xx] != 0)
					continue;

				cnt++;
			}

			if (secondCnt < cnt) {
				secondCandidate.clear();
				secondCandidate.add(p);
				secondCnt = cnt;
			} else if (secondCnt == cnt) {
				secondCandidate.add(p);
			}
		}

		Pair p = secondCandidate.get(0);
		board[p.y][p.x] = no;
		return;

	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 각 학생 별로 번호, 선호 학생 정보를 갖고 있는데 이를 어떻게 처리할지 생각해야 했다.

2. HashMap에 <번호, 선호 학생 리스트>로 저장할 생각을 했었다.

3. 하지만 학생 리스트를 no로 오름차순 정렬하면, no로 특정 학생 정보에 접근할 수 있었다.