[Algorithm] 백준 2304 - 창고 다각형 (Node / C#)

문제

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

풀이

1. Node.js(fs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 기둥의 개수 파싱
const N = parseInt(input[0]);

// 기둥 정보 파싱 및 정렬
const pillars = input.slice(1).map(line => {
    const [L, H] = line.split(' ').map(Number);
    return { L, H };
}).sort((a, b) => a.L - b.L);

// 가장 높은 기둥 찾기
let maxHeight = 0;
let maxIndex = 0;
pillars.forEach((pillar, index) => {
    if (pillar.H > maxHeight) {
        maxHeight = pillar.H;
        maxIndex = index;
    }
});

let area = 0;
let currentHeight = 0;

// 왼쪽에서 최고 높이 기둥까지 계산
for (let i = 0; i <= maxIndex; i++) {
    if (pillars[i].H > currentHeight) {
        currentHeight = pillars[i].H;
    }
    if (i < maxIndex) {
        area += currentHeight * (pillars[i + 1].L - pillars[i].L);
    }
}

currentHeight = 0;

// 오른쪽에서 최고 높이 기둥까지 계산
for (let i = N - 1; i > maxIndex; i--) {
    if (pillars[i].H > currentHeight) {
        currentHeight = pillars[i].H;
    }
    area += currentHeight * (pillars[i].L - pillars[i - 1].L);
}

// 최고 높이 기둥의 면적 추가
area += maxHeight;

console.log(area);

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];
rl.on('line', (line) => {
  input.push(line);
}).on('close', () => {
  const n = parseInt(input[0]);
  const pillars = input.slice(1).map(line => line.split(' ').map(Number));

  pillars.sort((a, b) => a[0] - b[0]); // 위치 기준으로 정렬

  let maxH = 0;
  let maxIndex = 0;
  pillars.forEach(([L, H], idx) => {
    if (H > maxH) {
      maxH = H;
      maxIndex = idx;
    }
  });

  let area = 0;
  let currentH = 0;
  for (let i = 0; i <= maxIndex; i++) {
    if (pillars[i][1] > currentH) {
      currentH = pillars[i][1];
    }
    area += currentH;
  }

  currentH = 0;
  for (let i = n - 1; i > maxIndex; i--) {
    if (pillars[i][1] > currentH) {
      currentH = pillars[i][1];
    }
    area += currentH;
  }

  area += maxH;

  console.log(area);
});

3. C#

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        var pillars = new (int L, int H)[N];

        for (int i = 0; i < N; i++)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            pillars[i] = (input[0], input[1]);
        }

        Array.Sort(pillars, (a, b) => a.L.CompareTo(b.L));

        int maxHeight = 0, maxIndex = 0;
        for (int i = 0; i < N; i++)
        {
            if (pillars[i].H > maxHeight)
            {
                maxHeight = pillars[i].H;
                maxIndex = i;
            }
        }

        int area = 0;
        int currentHeight = 0;

        for (int i = 0; i <= maxIndex; i++)
        {
            if (pillars[i].H > currentHeight)
            {
                currentHeight = pillars[i].H;
            }
            if (i < maxIndex)
            {
                area += currentHeight * (pillars[i + 1].L - pillars[i].L);
            }
        }

        currentHeight = 0;

        for (int i = N - 1; i > maxIndex; i--)
        {
            if (pillars[i].H > currentHeight)
            {
                currentHeight = pillars[i].H;
            }
            area += currentHeight * (pillars[i].L - pillars[i - 1].L);
        }

        area += maxHeight;

        Console.WriteLine(area);
    }
}

 

설명

1. 기둥 정렬
   
   • 기둥을 위치(L) 기준으로 정렬합니다.
2. 최고 높이 기둥 찾기:
   • 가장 높은 기둥을 찾고 그 기둥의 인덱스를 기록합니다.
3. 면적 계산:
   • 왼쪽에서 최고 높이 기둥까지의 면적을 계산합니다.
   • 오른쪽에서 최고 높이 기둥까지의 면적을 계산합니다.
   • 최고 높이 기둥의 면적을 더합니다.
4. 최종 출력:
   • 창고 다각형의 총 면적을 출력합니다.