창고 다각형 - 백준 2304 (Java)

 

https://www.acmicpc.net/problem/2304

 

처음 풀이

 

1. 기둥 정보 입력 받아 각 기둥에 대해 Pole 객체를 만들고 List에 저장, 위치를 기준으로 정렬

 

static class Pole {
    int location;
    int height;

    public Pole(int location, int height) {
        this.location = location;
        this.height = height;
    }
}

public static void main(String[] args) throws IOException {

    int totalPole = Integer.parseInt(bf.readLine());

    StringTokenizer st = null;

    List<Pole> poleList = new ArrayList<>();

    for (int i = 0; i < totalPole; i++) {
        st = new StringTokenizer(bf.readLine(), " ");
        int location = Integer.parseInt(st.nextToken());
        int height = Integer.parseInt(st.nextToken());

        poleList.add(new Pole(location, height));
    }//for end

    //기둥을 위치를 기준으로 정렬
    poleList.sort(new Comparator<Pole>() {
        @Override
        public int compare(Pole p1, Pole p2) {
            return Integer.compare(p1.location, p2.location);
        }
    });

 

2. 최대 높이 기둥의 인덱스와 높이 구하기

 

for (int i = 0; i < totalPole; i++) {
    Pole pole = poleList.get(i);
    if (maxHeight<pole.height) {
        maxHeight = pole.height;
        maxHeightIdx = i;
    }
}//for end

 

 

3. 최대 높이 기둥을 중심으로 왼쪽 방향, 오른쪽 방향으로 나눠서 진행한다.

 

(왼쪽 방향)

- 남은 왼쪽 기둥 중 최대 높이의 기둥의 높이와 인덱스를 구한다.

- 위에서 구한 남은 기둥 중 최대 높이 * (직전 최대 높이 기둥의 위치 - 위에서 구한 최대 높이 기둥의 위치) 로 넓이를 구한다.

- 위 과정을 인덱스가 0이 될 때까지 진행한다.

 

(오른쪽 방향)

왼쪽 방향과 같은 방식으로 진행한다

대신 넓이를 구할 때 (위에서 구한 최대 높이 기둥의 위치 - 직전 최대 높이 기둥의 위치)가 되어야 한다.

위 과정을 인덱스가 마지막 인덱스가 될 때까지 진행하면 된다.

 

넓이의 합인 sum은 최대 높이 기둥 1개의 넓이로 초기값을 준다. (이후 같은 높이의 기둥이 여러 개 있다고 하더라도 위 과정을 통해 처리 가능)

 

int maxLeftHeight = 0;
int maxLeftPrevIdx = 0;
int maxLeftIdx = maxHeightIdx;
int maxRightHeight = 0;
int maxRightPrevIdx = 0;
int maxRightIdx = maxHeightIdx;

int sum = maxHeight;

//왼쪽
while (maxLeftIdx!=0) {
    maxLeftHeight = 0;
    maxLeftPrevIdx = maxLeftIdx;
    for (int i = 0; i < maxLeftPrevIdx; i++) {
        Pole now = poleList.get(i);
        if (maxLeftHeight < now.height) {
            maxLeftHeight = now.height;
            maxLeftIdx = i;
        }
    }//for end
    sum += maxLeftHeight * (poleList.get(maxLeftPrevIdx).location-poleList.get(maxLeftIdx).location);
}//while end

//오른쪽
while (maxRightIdx!=totalPole-1) {
    maxRightHeight = 0;
    maxRightPrevIdx = maxRightIdx;
    for (int i = maxRightPrevIdx+1; i < totalPole; i++) {
        Pole now = poleList.get(i);
        if (maxRightHeight < now.height) {
            maxRightHeight = now.height;
            maxRightIdx = i;
        }
    }//for end
    sum += maxRightHeight * (poleList.get(maxRightIdx).location-poleList.get(maxRightPrevIdx).location);
}//while end

 

 

개선한 풀이

 

넓이를 새로 채울 때마다, 매번 남은 기둥 중 최대 높이 기둥을 구하는 루틴이 비효율적이다.

최대 높이 기둥을 사이에 두고 왼쪽 끝과 오른쪽 끝에서 넓이를 채워오는 방식으로 개선했다.

 

(왼->오)

- 인덱스 0부터 왼->오로 이동하면서, 현재 기둥이 전 기둥 높이보다 높으면 (전 기둥 높이 * 전 기둥부터 현 기둥까지의 위치 차이)를 넓이에 더해준다.

- 이 과정을 전체 최대 높이 기둥까지 진행한다.

 

(오->왼)

- 마지막 인덱스부터 오->왼으로 이동하면서 같은 방식으로 진행한다.

- 이 과정을 전체 최대 높이 기둥까지 진행한다.

 

마지막으로 최대 높이 기둥에 해당하는 넓이를 더해준다.

 

int sum = 0;

int maxHeightPoleIdx = 0;
Pole roofPole = poleList.get(0);

//왼쪽 -> 오른쪽
for (int i = 1; i < totalPole; i++) {
    Pole nowPole = poleList.get(i);
    if (roofPole.height <= nowPole.height) {
        sum += roofPole.height * (nowPole.location - roofPole.location);

        roofPole = nowPole;
        maxHeightPoleIdx = i;
    }
}//for end


roofPole = poleList.get(poleList.size()-1);
//오른쪽 -> 왼쪽
for (int i = poleList.size()-2; i > maxHeightPoleIdx-1; i--) {
    Pole nowPole = poleList.get(i);
    if (roofPole.height <= nowPole.height) {
        sum += roofPole.height * (roofPole.location - nowPole.location);

        roofPole = nowPole;
    }
}//for end

sum += roofPole.height;