[Java] swea 4014 활주로 건설

[Java] swea 4014 활주로 건설

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

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

public class 모의SW_4014_활주로건설 {
	static int N, X;
	static int[][] grid;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = Integer.parseInt(st.nextToken());
			grid = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					grid[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			System.out.println("#" + testcase + " " + solve());
		} // tc

	} // main

	private static int solve() {
		int COUNT = 0;
		// 가로
		for (int i = 0; i < N; i++) {
			if(canMakeRoad(grid[i])) {
				COUNT++;
			}
		} // i
		
		
		// 세로
		for (int j = 0; j < N; j++) {
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = grid[i][j];
			}
			if(canMakeRoad(arr)) {
				COUNT++;
			}
		}
		
		return COUNT;
	} // solve

	static boolean canMakeRoad(int[] arr) {
		int now = arr[0];
		int cnt = 1;
		List<Integer> list = new ArrayList<>();	// 설치한 인덱스 추가
		
		for (int i = 1; i < N; i++) {
			if (now == arr[i])
				cnt++;
			else if (now + 1 == arr[i]) {
				if (cnt < X) return false;
				
				int idx = i-1;
				int runCnt = X;
				while(true) {
					if(runCnt <= 0) break;
					if(list.contains(idx)) return false;
					list.add(idx--);
					runCnt--;
				}
				now = arr[i];
				cnt = 1;
			} else if (now - 1 == arr[i]) {
				int cnt2 = 1;
				list.add(i);
				for (int j = i + 1; j < N; j++) {
					if (now - 1 == arr[j]) {
						list.add(j);
						cnt2++;
					}
					else break;
					if (cnt2 >= X) {
						now = arr[j];
						i = j;
						break;
					}
				}
				if (cnt2 < X) return false;
				cnt=1;
			} else
				return false;
		}

		return true;
	} // road
}

가로 세로를 체크해야하므로 배열을 떼서 1차원 배열로 함수 실행하는 것이 훨씬 편하다.

배열을 받으면 canMakeRoad 함수에서, 자기보다 1 크거나 1 작은 애들이 보일 때까지 체크한다.

만약 2 이상 크거나 2 이하 작은 애들이 있으면 무조건 활주로 건설할 수 없으므로 바로 return false

나보다 큰 애들은 어차피 i를 올리면서 개수를 체크할 수 있으니까 cnt 변수로 높이 같은 애들이 몇 개였는지 기억하고 있는다.

만약 나보다 1 큰 애가 나왔으면 거쳐온 애들 중 cnt가 길이 X 이상이라면 활주로를 놓을 수 있으니 그대로 진행

cnt 가 X 보다 작다면 놓을 수 없으니 return false

만약 나보다 1 작은 애가 나왔으면 작은애들이 연속 된 개수가 X 이상이어야하므로 for 문 돌려서 체크해본다.

이렇게 끝까지 배열 가면 활주로 놓을 수 있는 배열이다.

내가 생각하지 못하고 틀려서 마지막에 바꾼내용은 list로 이미 활주로를 놓은 칸을 기억하는 것이다.

활주로를 중복하여 놓을 수 없기 때문에 활주로를 놓기 전에 list.contain 으로 확인해보고 놓아져있다면,,
return false 해야한다.