📝문제

이번 네이버 코테에 빡구현 문제들이 나와서 구현 문제를 풀어보았다.
우선 문제를 보자마자 음..구현이군 싶었고, 좋아하는 학생들에 포함되는지를 쉽게 판단하기 위해 Set 자료구조를 사용해야 될 거 같다고 생각했다.
처음에는

Set<Integer>[] like = new Set[student];

이렇게 선언했는데 NullPointer 에러가 났다.
Set타입을 원소로 가지는 배열을 만들기 위해서는 ArrayList와 Set을 같이 사용하여 각 ArrayList의 원소를 HashSet으로 초기화시켜줘야한다.

그 뒤로는 진짜 빡구현이다. 정말 오랜만에 3중첩↑ for문을 사용해보았다. 코테에서 for문을 3번 이상 중첩할 거 같으면 다른 방법을 찾아보는데, 이 문제는 다른 해결방법이 생각나지 않았다.
근데 코드 채점에서 시간초과 날 거 같았는데 통과했다! 다음에 코테 볼 때도 알고리즘이 떠오르지 않고 구현이다 싶으면 for문이 많이 중첩되어도 그 방법으로 시도해봐야겠다.

📌코드

package Baekjoon;

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

public class BOJ21608 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int student = n * n; //학생 수
        //좋아하는 학생에 포함되는지 쉽게 파악하기 위해서 Set 사용
        ArrayList<Set<Integer>> like = new ArrayList<>();
        for(int i = 0; i < student+1; i++){
            like.add(new HashSet<>());
        }
        int[] orders = new int[student];
        StringTokenizer st;
        for(int i = 0; i < student; i++){
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            orders[i] = cur;
            for(int j = 0; j < 4; j++){
                like.get(cur).add(Integer.parseInt(st.nextToken()));
            }
        }
        ////인접한 칸
        int[] moveX = {-1, 0, 1, 0};
        int[] moveY = {0, -1, 0, 1};
        int[][] seat = new int[n][n];
        int sx=0, sy=0, maxW, weight=0;
        for(int s = 0; s < orders.length; s++){
            maxW = -1;
            //[0][0]부터 각 자리마다 탐색하면서 해당 자리에 대한 가중치를 매기고, 위치를 저장한다
            for(int i = 0; i < seat.length; i++){
                for(int j = 0; j < seat[i].length; j++){
                    //해당 자리에 이미 학생이 앉아있다면 패스
                    if(seat[i][j] != 0) continue;
                    //인접한 곳을 탐색하면서 가중치를 매긴다
                    weight = 0;
                    for(int k = 0; k < 4; k++){
                        int curX = j + moveX[k];
                        int curY = i + moveY[k];
                        if(isSeat(curX, curY, n)){
                            //인접한 곳에 좋아하는 학생이 있으면 +10 (1순위)
                            if(like.get(orders[s]).contains(seat[curY][curX])) weight+=10;
                            //비어있는 곳이라면 +1 (2순위)
                            else if(seat[curY][curX] == 0) weight+=1;
                        }
                    }
                    //해당 자리에 대한 가중치
                    if(weight > maxW){
                        sx = j;
                        sy = i;
                        maxW = weight;
                    }
                }
            }
            //학생의 자리 결정
            seat[sy][sx] = orders[s];
        }
        int answer = 0;
        for(int i = 0; i < seat.length; i++){
            for(int j = 0; j < seat[i].length; j++){
                int cnt = 0;
                for(int k = 0; k < 4; k++){
                    int curX = j + moveX[k];
                    int curY = i + moveY[k];
                    if(isSeat(curX, curY, n) && like.get(seat[i][j]).contains(seat[curY][curX])) cnt+=1;
                }
                if(cnt == 0) continue;
                answer += Math.pow(10, cnt-1);
            }
        }
        System.out.println(answer);
    }

    //자리 범위 안에 속하는지 확인
    public static boolean isSeat(int x, int y, int n){
        return x >= 0 && x < n && y >= 0 && y < n;
    }
}