백준 - 2304 창고 다각형 [구현]

 

2304번: 창고 다각형

1. 문제 요약

주어진 좌표와 높이에 맞는 다각형의 넓이를 구하라(단, 오목하게 들어가는 부분은 없어야 한다.)

 

2. 파이썬

조금 비효율적인 방식으로 처음에 풀었습니다 ...ㅎ

 

2 - 1. 접근 방법

• 주어진 좌표와 높이에서 가장 큰 부분에 맞는 이중배열을 생성
• 현재 높이와 이전의 높이 중 가장 높은 높이로 이중배열을 채워준다
• 동일한 방식으로 좌표 역순으로 진행
• 생성된 두 이중배열을 비교하여 둘 다 채워진 경우 넓이를 증가 시킨다

 

2 - 2. 코드

def solution(cols: int, rows: int):
    answer = 0
    arr_left = [[0] * (cols + 2) for _ in range(rows + 2)]
    arr_right = [[0] * (cols + 2) for _ in range(rows + 2)]

    for pillar in pillars:
        arr_left[pillar[1]][pillar[0]] += 1
        arr_right[pillar[1]][pillar[0]] += 1

    for y in range(rows, 0, -1):
        for x in range(1, cols + 1):
            if arr_left[y][x - 1] == 1 or arr_left[y + 1][x] == 1:
                arr_left[y][x] = 1

    for y in range(rows, 0, -1):
        for x in range(cols, 0, -1):
            if arr_right[y][x + 1] == 1 or arr_right[y + 1][x] == 1:
                arr_right[y][x] = 1

            if arr_left[y][x] == 1 and arr_right[y][x] == 1:
                answer += 1

    print(answer)

n = int(input())
pillars = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]

rows = max(pillar[1] for pillar in pillars)
cols = max(pillar[0] for pillar in pillars)

solution(cols, rows)

 

3. 자바

이전 높이를 기록하는 방식으로 정방향, 역방향, 중간으로 나누어 진행하는 방식으로 최적화해보았습니다.

 

3 - 1. 접근 방법

• 좌표를 순서대로 정렬한다.
• 정방향으로 가장 높은 부분 직전까지의 넓이를 계산한다. (이때 가장 높은 부분을 만난 지점을 기록)
• 위와 마찬가지로 역방향으로 진행하며 넓이를 계산한다.
• 정방향과 역방향으로 진행하며 멈춘 부분을 이용하여 중간 부분의 넓이를 계산한다.

 

3 - 2. 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] pillars = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] num = br.readLine().split(" ");
            pillars[i][0] = Integer.parseInt(num[0]);
            pillars[i][1] = Integer.parseInt(num[1]);
        }
        
        System.out.println(solution(n, pillars));
    }

    static int solution(int n, int[][] pillars) {
        Arrays.sort(pillars, Comparator.comparingInt(pillar -> pillar[0]));
        int max = getMax(pillars);
        int answer = 0;

        // 정방향
        int[] prefixA = new int[]{pillars[0][0], pillars[0][1]};
        for (int i = 1; i < n; i++) {
            answer += (pillars[i][0] - prefixA[0]) * prefixA[1];
            prefixA[0] = pillars[i][0];
            prefixA[1] = Math.max(prefixA[1], pillars[i][1]);
            if (prefixA[1] == max) {
                break;
            }
        }

        // 역방향
        int[] prefixB = new int[]{pillars[n - 1][0], pillars[n - 1][1]};
        for (int i = n - 2; i >= 0; i--) {
            answer += (prefixB[0] - pillars[i][0]) * prefixB[1];
            prefixB[0] = pillars[i][0];
            prefixB[1] = Math.max(prefixB[1], pillars[i][1]);
            if (prefixB[1] == max) {
                break;
            }
        }

        // 중간
        answer += (prefixB[0] - prefixA[0] + 1) * max;

        return answer;
    }

    static int getMax(int[][] arr) {
        int max = Integer.MIN_VALUE;
        for (int[] ints : arr) {
            if (ints[1] > max) {
                max = ints[1];
            }
        }
        return max;
    }
}

 

4. 깃허브 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/2304.%E2%80%85%EC%B0%BD%EA%B3%A0%E2%80%85%EB%8B%A4%EA%B0%81%ED%98%95