[코딩 테스트 RUN] SWEA 수업 : 1206.View

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

문제 전문은 이렇다.

 

[SW Expert Academy] 1206. [S/W 문제해결 기본] 1일차 - View

SW Expert Academy

 

요약을 하면, 조망권이 확보되기 위해서는 거리 2이상의 공간이 확보될 때를 의미하는 것이다. 즉, 양옆으로다. 내가 처음 설계를 잘못한 건 아래로 두칸이라고 생각했기 때문이었다. 즉, 조망권이 확보되려면 층 본인보다 낮은 세대가 왼쪽 2곳, 오른쪽 2곳에 있어야 한다는 것이다.

 

처음 제출은 이것이었다.

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

class Solution {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			int n = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int count = st.countTokens();
			int[] arr = new int[count];
			int house = 0;

			for (int i = 0; i < arr.length; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			for (int i = 2; i < arr.length - 2; i++) {
				int a = arr[i] - arr[i - 1];
				int b = arr[i] - arr[i + 1];
				int min = (int) Math.min(a, b);
				if (min >= 2) {
					house += min - 1;
				}
			}

			System.out.println("#" + test_case + " " + house);
		}
	}
}

 

런타임 에러가 났는데, 그 이유는 테스트 케이스가 10개라는 걸 보지 못했기 때문. 하지만 그걸 제외하더라도 심각한 문제가 있다. 글을 잘못 읽었기 때문에 아래로 2칸이 형성되어야 한다고 되어있다.

다만 그것들을 제외하면 이미 괜찮은 지점이라 그부분만 집어보겠다.

 

나머지 부분들은 최적화를 위한 작업이기 때문에 넘어간다면(물론 배열화는 반드시 해야한다. 이 문제의 핵심은 배열화이기 때문에), 핵심은 여기이다.

 

			for (int i = 2; i < arr.length - 2; i++) {
				int a = arr[i] - arr[i - 1];
				int b = arr[i] - arr[i + 1];
				int min = (int) Math.min(a, b);
				if (min >= 2) {
					house += min - 1;
				}
			}

 

여기서 for문의 시작점과 끝점이 중요한데, 왼쪽 2칸과 오른쪽 2칸은 시작하지 않는다는 것. 그곳은 건물이 지어지지 않는다는 제한이 있다. 그러므로 for문의 시작점과 끝점에서 제외한다.

글을 잘못 읽은 입장에서 보다시피 arr[i]의 전과 후에서 min값을 골라 그걸 house에 추가했다. 이렇게 하면 단차의 최소가 맞춰지기 때문이다. 다만 min - 1을 한 이유는 포함되지 않는 세대도 추가하기 때문에(딱 경계선 위치) 그 부분을 제거해주는 작업이었다.

 

물론 문제를 잘못 읽어서 틀렸다.

 

다행히도 이 for문 안만 고쳐주면 된다. 다음과 같다.

 

            for (int i = 2; i < arr.length - 2; i++) {
                int left1 = arr[i - 1];
                int left2 = arr[i - 2];
                int right = arr[i + 1];
                int right2 = arr[i + 2];


                int max = Math.max(Math.max(left1, left2), Math.max(right, right2));
                if (arr[i] > max) {
                    house += arr[i] - max;
                }
            }

 

구하려는 세대(i)에서 -2와 +2세대를 구분한다. for의 조건 덕분에 경계선 오류를 걱정할 필요는 없다.

그리고 이 중 max값을 구한다. 왜냐하면 이것이 확보된 세대의 최저 기준점이 되어줄 예정이기 때문이다.

양이 많으므로 if문을 쓰기보단 Math.max를 사용했다.

구하려는 세대(i)가 max값보다 높을 경우에만 세대에 더한다. 그러면 종료된다. 쉬운 문제.