(Java) 4014. [모의 SW 역량테스트] 활주로 건설

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

– 가로/세로의 경우 로직은 기본적으로 동일하고 2차원 map array에서 순회하는 방향만 다름.
– 각 줄의 경우 (가로/세로) 높이/길이 그룹화를 시킴. (높이 차이가 1이 넘는 경우는 미리 필터링)
– 그룹화된 데이터를 기반으로, 높아질 때는 설치할 수 없을 때 (기존 위치) 필터링함. 낮아질 때는 설치할 수 없을 때 (현재 위치) 필터링하고 현재 위치의 길이를 K (경사로 폭)만큼 감소 (경사로를 두 개 설치해야 할 때 확인 필요).
– 필터링이 안 된 경우에만 가능한 갯수로 카운트

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

public class Solution {	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // 맵 크기 
				int numX = Integer.parseInt(tmp[1]); // 경사로 폭
				
				// Map 생성
				int[][] map = new int[numN][numN];
				for (int i = 0; i < numN; i++) {
					String[] tmp_ = reader.readLine().split(" ");
					
					for (int j = 0; j < tmp_.length; j++)
						map[j][i] = Integer.parseInt(tmp_[j]);
				}
				
				int answer = 0;
				
				// 가로 처리
				for (int i = 0; i < numN; i++) {
					boolean available = true;
					int currentHeight = 0; // 현재 높이
					int currentCount = 0;  // 현재 높이가 이어지는 갯수
					
					Queue<Integer> heightList = new LinkedList<Integer>(); // 높이 목록
					Queue<Integer> countList = new LinkedList<Integer>();  // 갯수 목록
					
					// 최초값 처리
					currentHeight = map[0][i];
					currentCount++;
					
					// 높이/길이 그룹화
					for (int j = 1; j < numN; j++) {
						if (map[j][i] == currentHeight) // 높이가 같은 경우
							currentCount++;
						else {	// 높이가 달라지는 경우
							if (map[j][i] == currentHeight + 1 || map[j][i] == currentHeight - 1) { // 1 차이 나는 경우							
								heightList.add(currentHeight);
								countList.add(currentCount);
								
								currentHeight = map[j][i];
								currentCount = 1;
							}
							else { // 높이 차이가 1이 아닌 경우 아예 불가능
								available = false;
								break;
							}
						}
					}
					
					// 애초에 불가능한 경우 진행하지 않음
					if (available == false)
						continue;
					
					// 마지막 정보도 투입
					heightList.add(currentHeight);
					countList.add(currentCount);
					
					// 높이가 하나만 있는 경우 
					if (heightList.size() == 1) {
						answer++;
						continue;
					}

					int prevHeight = 0;
					int prevCount = 0; 

					currentHeight = heightList.poll();
					currentCount = countList.poll();
					
					while (heightList.size() > 0) {
						prevHeight = currentHeight;
						prevCount = currentCount;
						
						currentHeight = heightList.poll();
						currentCount = countList.poll();
						
						if (prevHeight < currentHeight) { // 현재  높이가 1 더 높은 경우
							if (prevCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
						}
						if (prevHeight > currentHeight) { // 현재 높이가 1 더 낮은 경우
							if (currentCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
							
							currentCount -= numX; // 높->낮(현재)->높이 될 때 낮은 위치의 길이가 두 경사로를 설치할 수 있는지 체크하기 위함 
						}
					}

					if (available == true)
						answer++;
				}
				
				// 세로 처리 
				for (int i = 0; i < numN; i++) {
					boolean available = true;
					int currentHeight = 0; // 현재 높이
					int currentCount = 0;  // 현재 높이가 이어지는 갯수
					
					Queue<Integer> heightList = new LinkedList<Integer>(); // 높이 목록
					Queue<Integer> countList = new LinkedList<Integer>();  // 갯수 목록
					
					// 최초값 처리
					currentHeight = map[i][0];
					currentCount++;
					
					for (int j = 1; j < numN; j++) {
						if (map[i][j] == currentHeight) // 높이가 같은 경우
							currentCount++;
						else {	// 높이가 달라지는 경우
							if (map[i][j] == currentHeight + 1 || map[i][j] == currentHeight - 1) { // 1 차이 나는 경우
								heightList.add(currentHeight);
								countList.add(currentCount);
								
								currentHeight = map[i][j];
								currentCount = 1;
							}
							else { // 높이 차이가 1이 아닌 경우 아예 불가능
								available = false;
								break;
							}
						}
					}
					
					// 애초에 불가능한 경우 진행하지 않음
					if (available == false)
						continue;

					// 마지막 정보도 투입
					heightList.add(currentHeight);
					countList.add(currentCount);
					
					// 높이가 하나만 있는 경우 
					if (heightList.size() == 1) {
						answer++;
						continue;
					}

					int prevHeight = 0;
					int prevCount = 0; 

					currentHeight = heightList.poll();
					currentCount = countList.poll();
					
					while (heightList.size() > 0) {
						prevHeight = currentHeight;
						prevCount = currentCount;
						
						currentHeight = heightList.poll();
						currentCount = countList.poll();
						
						if (prevHeight < currentHeight) { // 현재 높이가 1 더 높은 경우
							if (prevCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
						}
						else if (prevHeight > currentHeight) { // 현재 높이가 1 더 낮은 경우
							if (currentCount < numX) { // 낮은 쪽 (현재) 폭이 좁을 경우
								available = false;
								break;
							}
							
							currentCount -= numX; // 높->낮(현재)->높이 될 때 낮은 위치의 길이가 두 경사로를 설치할 수 있는지 체크하기 위함 
						}
					}
										
					if (available == true) 
						answer++;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.