백준 21608 상어초등학교

시간 /메모리 효율 둘 다 썩 좋지 않은 코드.

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

public class 상어초등학교 {
	static class Shark implements Comparable<Shark>{
		int num; // 번호
		int r; // 행
		int c; // 열
		int likeCnt; // 좋아하는 학생
		int blankCnt; // 비어있는 칸
		List<Integer> likeFriends; // 좋아하는 학생번호 리스트
		
		
		Shark(int num, int r, int c, int likes, int blanks, List<Integer> likeFriends) {
			this.num = num;
			this.r = r;
			this.c = c;
			this.likeCnt = likes;
			this.blankCnt = blanks;
			this.likeFriends = likeFriends;
		}

		@Override
		public int compareTo(Shark o) {
			if(this.likeCnt != o.likeCnt) return this.likeCnt - o.likeCnt;
			if(this.blankCnt != o.blankCnt) return this.blankCnt - o.blankCnt;
			if(this.r != o.r) return o.r - this.r;
			if(this.c != o.c)return o.c - this.c; 
			return 0;
		}
	}
	
	static int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	static int answer;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Shark[][] map = new Shark[N][N];
		
		for(int n = 0; n < N * N; n++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int aa = Integer.parseInt(st.nextToken());
			int bb = Integer.parseInt(st.nextToken());
			int cc = Integer.parseInt(st.nextToken());
			int dd = Integer.parseInt(st.nextToken());

			List<Integer> likeFriends = new ArrayList<>(); // 좋아하는 학생 번호 리스트
			likeFriends.add(aa);
			likeFriends.add(bb);
			likeFriends.add(cc);
			likeFriends.add(dd);
			
			List<Shark> sharkList = new ArrayList<>(); // 학생(Shark)들 담을 리스트
			
			for(int r = 0; r < N; r++) {
				for(int c = 0; c < N; c++) {
					int likeCnt = 0;
					int blankCnt = 0;
					
					if(map[r][c] != null) continue; // (r,c) 좌표에 이미 학생 앉아있다면 -> continue
					
					for(int d = 0; d < deltas.length; d++) { // 인접칸 탐색
						int nr = r + deltas[d][0];
						int nc = c + deltas[d][1];
						
						if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
						
						if(map[nr][nc] == null) { // 인접칸 중 비어있는 칸 count
							blankCnt++;
							continue;
						}
						
						if(likeFriends.contains(map[nr][nc].num)) // 인접 칸 중 좋아하는 학생 있는 칸 count
							likeCnt++;
					}
					
					sharkList.add(new Shark(num, r, c, likeCnt, blankCnt, likeFriends));
				}
			}
			
			Collections.sort(sharkList); // likeCnt -> blankCnt -> r -> c 순으로 정렬
			Shark shark = sharkList.get(sharkList.size()-1);
			map[shark.r][shark.c] = shark; // 교실에 상어 앉히기
			sharkList.clear(); // 리스트 초기화
		}
		
		findSatisfy(map, N);
		
		System.out.println(answer);
	}
	
	static void findSatisfy(Shark[][] map, int N) {
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				List<Integer> list = map[r][c].likeFriends;
				int cnt = 0;
				for(int d = 0; d < deltas.length; d++) {
					int nr = r + deltas[d][0];
					int nc = c + deltas[d][1];
					if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
					
					if(list.contains(map[nr][nc].num))
						cnt++;
				}

				if(cnt == 0) answer += 0;
				if(cnt == 1) answer += 1;
				if(cnt == 2) answer += 10;
				if(cnt == 3) answer += 100;
				if(cnt == 4) answer += 1000;
			}
		}
	}
}