[알고리즘]백준 2304: 창고다각형, 백준 14719번: 빗물

해결방법

1. 기둥을 정렬한 후 가장 높은 기둥을 알아낸다.
2. 왼쪽 ~ 가장 높은 기둥까지 면적을 더한다. 왼쪽에서 가장 높은 기둥을 기준으로 가장 높은 기둥이 갱신될 때마다 면적을 더한다.
3. 오른쪽 ~ 가장 높은 기둥까지 위와 같은 로직을 반복한다.

⇒ 정렬에 O(Nlog), 면적을 더하는데 O(N)의 시간복잡도가 소요된다.

 

코드

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

// 112ms
public class Main_2304_S2_창고다각형 {
    static int N;
    static Tower[] tower;

    static class Tower{
        int w, h;

        public Tower(int w, int h){
            this.w=w;
            this.h=h;
        }
    }

    public static void main(String[] args) throws IOException {
        //1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        tower = new Tower[N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            tower[i] = new Tower(w,h);
        }
        Arrays.sort(tower, new Comparator<Tower>() {
            @Override
            public int compare(Tower o1, Tower o2) {
                return Integer.compare(o1.w, o2.w);
            }
        });

        //2.
        int highest = 0;
        for(int i=0; i<N; i++){
            if(tower[i].h>=tower[highest].h) highest = i;
        }
        // left ~ highest
        int answer = tower[highest].h;
        int left = 0;
        for(int i=1; i<=highest; i++) {
            if (tower[i].h >= tower[left].h) {
                int n = Math.min(tower[i].h, tower[left].h);
                answer += n * (tower[i].w - tower[left].w);
                if (tower[i].h >= tower[left].h) left = i;
            }
        }
        // highest ~ right
        int right = N-1;
        for(int i=N-2; i>=highest; i--){
            if (tower[i].h >= tower[right].h) {
                int n = Math.min(tower[i].h, tower[right].h);
                answer += n * (tower[right].w - tower[i].w);
                if (tower[i].h >= tower[right].h) right = i;
            }
        }

        //3. 출력
        System.out.println(answer);
    }
}

링크

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

 

 

해결방법

같은 로직에서 블록의 면적만 빼주면 된다.

 

코드

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

// 108ms
public class Main {
    static int H, W;
    static int[] block;

    public static void main(String[] args) throws IOException{
        //1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        block = new int[W];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<W; i++){
            block[i] = Integer.parseInt(st.nextToken());
        }

        //2. 로직 전체 면적  - 블록의 면적
        int highest = 0;
        for(int i=0; i<W; i++){
            if(block[i]>=block[highest]) highest=i;
        }
        int s = block[highest];
        int left = 0;
        for(int i=1; i<=highest; i++){
            if(block[i]>=block[left]){
                int n = Math.min(block[i],block[left]);
                s+=(n*(i-left));
                left = i;
            }
        }
        int right = W-1;
        for(int i=W-2; i>=highest; i--){
            if(block[i]>=block[right]){
                int n = Math.min(block[i],block[right]);
                s+=(n*(right-i));
                right = i;
            }
        }
        for(int i=0; i<W; i++){
            s-=block[i];
        }
        //3. 출력
        System.out.println(s);
    }
}

 

링크

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