[프로그래머스] JavaScript Lv1 - 최소직사각형(86491)

개요

문제 이름: 최소직사각형 (86491)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86491
플랫폼: 프로그래머스
알고리즘 분류: 완전탐색
소요 시간: 10분(...)

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 2차원 배열로 주어진 명함의 가로, 세로 길이를 이용하여 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 구하는 알고리즘 문제입니다.

 

문제 해결을 위해서는 다음과 같은 접근 방식을 사용할 수 있습니다.

1. 각 명함의 가로와 세로 길이를 비교하여 긴 쪽을 가로로, 짧은 쪽을 세로로 회전시킵니다.
2. 회전시킨 명함들 중 가장 긴 가로 길이와 가장 긴 세로 길이를 찾습니다.
3. 찾은 가장 긴 가로 길이와 세로 길이를 곱하여 지갑의 크기를 계산합니다.

이를 위해 배열 메서드인 map과 forEach를 사용할 수 있습니다.

• map: 배열의 각 요소에 대해 주어진 함수를 호출한 결과로 새로운 배열을 생성합니다.
• forEach: 배열의 각 요소에 대해 주어진 함수를 실행합니다.

또한, 구조 분해 할당과 삼항 연산자를 사용하여 코드를 간결하게 작성할 수 있습니다.

 

시도

1차 시도  (성공)

// 1차 시도 (성공)
function solution(sizes) {
	let result = [];
	sizes.map(([value]) => {
		value.sort((a, b) => a - b);
		result[0] < value[0] || !result[0] ? (result[0] = value[0]) : 0;
		result[1] < value[1] || !result[1] ? (result[1] = value[1]) : 0;
	});
	return result[0] * result[1];
}

1차 시도에서는 map 메서드를 사용하여 각 명함의 크기를 순회하면서 처리했습니다. 먼저 각 명함의 가로와 세로 길이를 오름차순으로 정렬하여 긴 쪽을 가로로, 짧은 쪽을 세로로 회전시켰습니다.

그 다음 result 배열을 사용하여 가장 긴 가로 길이와 세로 길이를 저장했습니다. 삼항 연산자를 사용하여 현재 명함의 가로, 세로 길이와 result에 저장된 값을 비교하여 더 큰 값을 result에 저장했습니다. 마지막으로 result에 저장된 가장 긴 가로 길이와 세로 길이를 곱하여 지갑의 크기를 계산하고 반환했습니다.

 

이 방법은 직관적이고 이해하기 쉽지만, 불필요한 연산이 포함되어 있습니다. 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.

 

2차 시도  (성공)

// 2차 시도 (성공)
function solution(sizes) {
	let result = [0, 0];
	sizes.forEach(([w, h]) => {
		let [min, max] = w > h ? [h, w] : [w, h];
		result[0] = Math.max(result[0], max);
		result[1] = Math.max(result[1], min);
	});
	return result[0] * result[1];
}

2차 시도에서는 forEach 메서드를 사용하여 각 명함의 크기를 순회하면서 처리했습니다. 구조 분해 할당을 사용하여 각 명함의 가로 길이 w와 세로 길이 h를 추출했습니다.

삼항 연산자를 사용하여 w와 h를 비교하여 긴 쪽을 max, 짧은 쪽을 min으로 할당했습니다. 그리고 result 배열의 첫 번째 요소에는 max 값 중 가장 큰 값을, 두 번째 요소에는 min 값 중 가장 큰 값을 저장했습니다. 이를 위해 Math.max 메서드를 사용하였습니다. 마지막으로 result에 저장된 가장 긴 가로 길이와 세로 길이를 곱하여 지갑의 크기를 계산하고 반환했습니다.

 

이 방법은 1차 시도에 비해 불필요한 연산을 제거하여 더 효율적입니다. 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.

 

3차 시도 (성공)

// 3차 시도 (성공)
function solution(sizes) {
	let result = [0, 0];
	let rotated = sizes.map(([w, h]) => (
        w < h ? [h, w] : [w, h]
    ));
    
	rotated.forEach(([w, h]) => {
		if (w > result[0]) result[0] = w;
		if (h > result[1]) result[1] = h;
	});
	return result[0] * result[1];
}

 

3차 시도에서는 map 메서드를 사용하여 각 명함의 크기를 회전시킨 새로운 배열 rotated를 생성했습니다. 구조 분해 할당과 삼항 연산자를 사용하여 가로 길이 w와 세로 길이 h를 비교하고, 긴 쪽을 가로로, 짧은 쪽을 세로로 회전시켰습니다.

 

그 다음 forEach 메서드를 사용하여 rotated 배열을 순회하면서 가장 긴 가로 길이와 세로 길이를 result 배열에 저장했습니다. if 문을 사용하여 현재 명함의 가로, 세로 길이와 result에 저장된 값을 비교하여 더 큰 값을 result에 저장했습니다. 마지막으로 result에 저장된 가장 긴 가로 길이와 세로 길이를 곱하여 지갑의 크기를 계산하고 반환했습니다.

이 방법은 회전된 명함들의 크기를 별도의 배열로 생성하여 코드의 가독성을 높였습니다. 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다.

 

사족

이 문제를 통해 배열 메서드와 구조 분해 할당, 삼항 연산자의 활용 방법을 익힐 수 있었습니다. 특히 구조 분해 할당에 대해 더 익힐 필요를 느꼈습니다.

 

그리고 문제 해결을 위해 주어진 데이터를 적절히 가공하고, 필요한 정보를 추출하여 원하는 결과를 도출하는 과정이 중요하다는 것 또한 알게 되었습니다.