문제 설명
다리 만들기 문제는 다음과 같습니다. 주어진 시민들은 ‘A’에서 ‘B’까지 가는 길에 다리를 하나 만들고 싶어합니다.
이 다리는 ‘A’와 ‘B’ 두 지점을 직접 연결하는 도로로 사용됩니다. 각 시민은 다리를 만들기 위해 여러 가지 점을 선택할 수 있으며,
각 점 사이의 거리는 미리 정해져 있습니다. 도시의 두 지점을 연결하는 가장 짧은 다리의 길이를 찾는 것이 문제입니다.
문제 입력
– 첫 번째 줄에는 점의 개수 n이 주어집니다 (1 ≤ n ≤ 1000).
– 두 번째 줄에는 각 점의 위치를 나타내는 정수 배열 positions이 주어집니다.
문제 출력
다리를 만들기 위해 필요한 최소 길이를 출력합니다.
예제 입력
5
1 2 4 5 10
예제 출력
9
문제 풀이 과정
이 문제를 해결하기 위해 가장 먼저 해야 할 일은 주어진 점들의 위치를 정렬하는 것입니다.
정렬된 위치의 첫 번째 점은 ‘A’의 위치를 대표하고, 마지막 점은 ‘B’의 위치를 대표합니다.
이렇게 하면 다리를 놓기 위해 이동해야 하는 총 거리를 쉽게 계산할 수 있습니다.
1단계: 입력 및 정렬
function buildBridge(positions) {
// 위치를 정렬
positions.sort((a, b) => a - b);
return positions;
}
2단계: 거리 계산
다음 단계로는 가장 첫 번째 점과 마지막 점 사이의 거리를 구하는 것입니다.
이는 다리의 길이를 결정짓는 가장 중요한 요소입니다.
function calculateBridgeLength(positions) {
const firstPoint = positions[0];
const lastPoint = positions[positions.length - 1];
return lastPoint - firstPoint;
}
3단계: 전체 함수 구현
이제 마지막으로 두 단계에서 구현한 부분을 통합하여 최종적으로 다리를 만들기 위해 필요한 전체 길이를 계산하는
함수를 완성하겠습니다.
function buildBridge(positions) {
// 위치를 정렬
positions.sort((a, b) => a - b);
// 첫 번째 점과 마지막 점
const firstPoint = positions[0];
const lastPoint = positions[positions.length - 1];
// 다리 길이 계산
return lastPoint - firstPoint;
}
// 예제 사용
const inputPositions = [1, 2, 4, 5, 10];
const bridgeLength = buildBridge(inputPositions);
console.log(bridgeLength); // 9
결론
이번 강의를 통해 주어진 문제를 해결하기 위해 어떻게 접근해야 하는지를 연습했습니다.
기본적인 배열 정리 및 길이 계산을 통해 제공된 입력으로부터 원하는 출력을 얻을 수 있었습니다.
이 방법론은 다른 알고리즘 문제를 해결하는 데에 있어 매우 유용합니다.
향후 더 어려운 문제들도 시도해 보세요!