[BOJ] 21608 : 상어 초등학교 (Java) with 정렬

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

21608번: 상어 초등학교

걸린 시간 : 1시간 4분

---

복잡한 문제같지만 자리를 주어진 조건에 맞게 정렬해서 한 명 한 명 자리에 앉히면 된다.

정렬

Java에서 복잡한 정렬을 하는 방법은 여러가지가 있다.

1. Comparator 인터페이스의 compare 함수를 직접 구현하기
2. 람다식을 활용해 익명 객체 사용해 구현하기
3. 메서드 참조와 유틸리티 메서드 사용하기

나는 2번을 이용해 문제를 풀었다.

아래는 int 형 변수 r, c를 가지는 클래스 Pos가 있을 때, posList를 정렬하는 코드이다. 이 때, r에 대해서 내림차순, 그 후 c에 대해서 올림차순 정렬하는 경우이다.

posList.sort((p1, p2) ->
        p1.r != p2.r ? p2.r - p1.r :
        p1.c - p2.c);

내림차순 정렬할 경우 p2에서 p1을 빼고, 올림차순의 경우 반대로 하면 된다.

알고리즘

1. (1, 1) 부터 (N, N) 까지의 Pos 형 인스턴스를 담는 리스트를 하나 만든다.
2. 학생을 차례대로 입력받으면서 어디에 앉힐 지 주어진 조건에 따라 리스트를 정렬시키며 결정한다. 앉힌 Pos 는 리스트에서 제거한다.
   이 때, 주변의 좋아하는 사람을 세는 메소드와 주변의 빈 칸을 세는 메소드를 따로 구현해 사용한다.
3. 모든 배치가 완료되면 학생마다 만족도를 계산해 출력한다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ21608 {

    static int N;
    static int score;
    static List<Pos> posList = new ArrayList<>();
    static int[][] loveList = new int[401][4];
    static int[][] students = new int[21][21];
    static int[] dr = {-1, 0, 0, 1};
    static int[] dc = {0, -1, 1, 0};
    static int[] scoreUtil = {0, 1, 10, 100, 1000};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                posList.add(new Pos(i, j));
            }
        }
        for (int i = 0; i < N*N; i++) {
            int[] love = new int[4];
            StringTokenizer st = new StringTokenizer(br.readLine());
            int studentNum = Integer.parseInt(st.nextToken());
            for (int j = 0; j < 4; j++) {
                love[j] = Integer.parseInt(st.nextToken());
            }
            loveList[studentNum] = love;
            posList.sort((p1, p2) ->
                    cntLove(p1, love) != cntLove(p2, love) ? cntLove(p2, love) - cntLove(p1, love) :
                            cntBlank(p1) != cntBlank(p2) ? cntBlank(p2) - cntBlank(p1) :
                            p1.r != p2.r ? p1.r - p2.r :
                            p1.c - p2.c);
            students[posList.get(0).r][posList.get(0).c] = studentNum;
            posList.remove(0);
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int studentNum = students[i][j];
                score += scoreUtil[cntLove(new Pos(i, j), loveList[studentNum])];
            }
        }
        System.out.println(score);
    }

    private static int cntBlank(Pos p1) {
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nr = p1.r + dr[k];
            int nc = p1.c + dc[k];
            if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
            for (int i = 0; i < 4; i++) {
                if (students[nr][nc] == 0) cnt++;
            }
        }
        return cnt;
    }

    private static int cntLove(Pos p1, int[] love) {
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nr = p1.r + dr[k];
            int nc = p1.c + dc[k];
            if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
            for (int i = 0; i < 4; i++) {
                if (students[nr][nc] == love[i]) cnt++;
            }
        }
        return cnt;
    }

    static class Pos {
        public int r, c;
        public Pos (int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}