[SW Expert Academy] 1206번 - View(조망권) 문제

 

SW Expert Academy

<내 사고과정>

입력값으로 들어온 빌딩들의 높이를 배열로 받아서 풀면 되겠다고 생각했다.

조망권이 확보된 세대의 기준은 좌우 모두 거리 2 이상의 공간이 확보된 상태를 말한다.

따라서 한 세대가 조망권이 확보되었는지, 아닌지를 따지기 위해서는

배열의 한 위치로부터 두칸 앞, 한칸 앞에 있는 건물 높이의 정보, 한칸 뒤, 두칸 뒤의 건물 높이의 정보를 파악하여

그중 가장 높은 높이를 가진 건물의 높이와의 차를 구하여(기준 건물 - 주변에서 가장 높은 건물 높이)푸는 식으로 하면 되겠다고 생각했다

즉 가장 작은 차를 구하면 되는 것이다

예를들어..기준이 되는 A라는 높이 10의 건물이 있다고 가정했을때 오른쪽 두칸 떨어진 건물 B의 높이가 8이고

나머지 건물들(두칸 앞, 한칸 앞, 한칸 뒤)의 높이가 모두 1이라고 쳤을때

나머지 건물들의 높이가 아무리 1이어도 B라는 높이 8의 건물이 조망을 가로막고 있기 때문에

결국 A 건물에서 조망권이 확보될 세대 수는 2가 된다.

앞뒤로 2개의 건물 높이만 살펴도 조망권 세대 개수는 판명나므로 나머지 건물의 높이는 고려하지 않아도 될 것이다.

따라서 코드에서 배열을 돌며 각 건물의 조망권 세대수를 계산할때 앞뒤로 두칸만 고려하도록 했다.

입력 조건에서 명시되어 있듯이, 입력값으로 오는 건물들의 높이는 맨 처음 두개와 맨 마지막 두개 높이가 0이 오므로

이 끝에있는 건물들을 포함하여 높이가 0인 건물들은 보나마나이기 때문에 높이가 0이면 if문으로 넘어가버리도록 했다.

풀이 전체 코드는 이러했다.

 

<내 풀이 코드>

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

public class SW_1206 {  //View, 조망권 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N;  //건물 개수
        int[] heights;  //각 건물의 높이를 뜻하는 배열 선언
        int views = 0;  //조망권 확보된 세대
        int min;    //앞의 두개, 뒤의 두개 건물들 중 가장 차이가 작은 값
        int temp = -2;

        for (int i = 0; i < 10; i++) {  //총 10개의 테스트게이스 입력받음
            N = Integer.parseInt(br.readLine());    //건물 개수를 의미하는 N을 입력받기
            heights = new int[N];   //그러고보니 한번 크기가 지정된 배열은 크기가 다시 바뀔수 없는걸로 아는데..어떻게 되는거지??
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                heights[j] = Integer.parseInt(st.nextToken());
            }
            views = 0;  //테스트케이스별로 view를 출력하므로 꼭 0으로 다시 초기화해준다
            for (int k = 0; k < N; k++) {
                min = heights[k]; temp = -2;  //min의 초기값을 뭘로 해야할지 고민아됐다
                if (heights[k] != 0) {  //가장 끝쪽에 있는 건물, 높이가 0인 건물들의 조망권 수는 카운트x
                    for (int h = 0; h < 5; h++) {   //앞뒤로 2개까지의 건물들과 크기 비교를 수행
                        if(h==2){
                            temp++;
                            continue;  //세번째 비교는 자기자신이므로 고려하면 안된다
                        }
                        if (heights[k] - heights[k + temp] < min) { //비교 중심이 되는 건물에서 비교할 건물들의 가장 작은 차를 구함
                            min = heights[k] - heights[k + temp];
                        }
                        temp++;
                    }
                    if (min > 0) {
                        views += min;   //min이 0 또는 음수라면 조망권이 하나도 없다는 의미, 아니라면 view에 누적시킨다
                    }
                }
            }
            bw.write("#" + (i+1) + " " + Integer.toString(views));
            bw.newLine();
        }
        bw.flush();
        bw.close();


    }
}

min값의 초기값을 heights[k]로 해주는 이유는,

만약 초기값을 0으로 한다고 가정했을때 주변 건물들과의 가장 작은 차가 1이라면 if조건문에 걸리지 않기 때문에

여전히 0으로 되어있게 될 것이다. 이는 잘못된 정보이므로 0으로 하지 않았다!

대신 heights[k]로 하게 된다면 어떤 경우더라도 최소한 기준 건물 높이인 heights[k]보다 큰 값이 올 일은 없으므로

제대로 min값이 들어오게 될 것이다 (첨에 무심코 0으로 했다가 잘못됐음을 꺠달음)

temp 초기값을 -2로 해놓는 이유는 다섯번 반복되는 for문의 안쪽 for문을 돌 때 temp가 증가되며 k-2, k-2, k(자기 자신과의 차는 고려하면 안되므로 이경우는 continue로 넘어가게 했다), k+1, k+2 순으로 k번째 배열값 앞뒤를 확인시키게 하기 위함이다!

 

늘 느끼지만, 문제를 보고 풀이법이 바로 대강 생각난다 하더라도 구체적으로 구현하는 과정에서 자잘하게 시간이 들어가는 부분이 많다는 점이다..초기값을 뭘로 줘야할지, 반복문 조건 등등 세심히 생각해야 할 부분들이 많다

 

다른 사람의 풀이법도 참고해서 분석해보자

밑에있는 코드는 다른 분의 풀이를 가져와서 조금 수정한 핵심 부분 코드이다.

for문의 j를 2로 시작하여 총 건물수 -2 이전까지 반복되게 하여 아예 총 건물수 -4번 반복되도록 했다.

그리고 크기 4의 배열을 하나 만들어 각 앞뒤 건물들과의 차를 구해 저장하고

그중 가장 작은값을 찾아 저장하는 방식이다. 가장 작은값을 구하기 위해 sort함수를 이용하였다.

for(int j=2; j<buildings.length-2; j++){
	int str[] = new int[4];	//앞뒤 4개의 건물 높이와의 차를 배열에 저장할것임
    str[0] = buildings[j] - buildings[j-2];
    str[0] = buildings[j] - buildings[j-1]; 
    str[0] = buildings[j] - buildings[j+1]; 
    str[0] = buildings[j] - buildings[j+2];
    
    Arrays.sort(str);	//str배열을 오름차순으로 정렬
    if(str[0] > 0){		//음수값이 아니라면 result에 누적시킨다
    	result += str[0];
    }

}

또는 밑에있는 코드처럼

먼저 max함수를 세번 사용하여 가장 큰 건물의 크기값을 찾고, 그 건물과의 차를 구해 tmp에 저장하는 방법도 있다.

for(int i=2;i<tc-2;i++)
    {
        tmp = map[i] - max(max(map[i-1], map[i-2]), max(map[i+1], map[i+2])); 

        if(tmp > 0)
            ret+=tmp;
    }

 

앞뒤로 2까지 중 가장 큰 높이의 건물을 찾는것, 즉 가장 작은 높이 차를 구하는것이 핵심인것!

원래의 내 코드보다 더 직관적이고 간결해서 좋은 것 같다.