개발일지/Algorithm
백준 - 2304 창고 다각형 [구현]
E-room
2023. 9. 22. 01:55
728x90
2304번: 창고 다각형
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의
www.acmicpc.net
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. 깃허브 전체 코드
728x90