[프로그래머스] JavaScript Lv2 - 멀쩡한 사각형(62048)

개요

문제 이름: 멀쩡한 사각형 (62048)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/62048
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 40분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 격자 형태로 그어진 직사각형 종이에서 대각선으로 잘라낸 후 사용할 수 있는 정사각형의 개수를 구하는 문제입니다. 문제 해결을 위해서는 전체 사각형의 개수에서 대각선에 의해 잘린 사각형의 개수를 빼는 방식을 사용할 수 있습니다.

 

문제에서 주어진 조건은 다음과 같습니다.

1. 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다.
2. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있습니다.
3. 모든 격자칸은 1cm x 1cm 크기입니다.
4. 누군가가 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.
5. 잘린 종이에서 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 정사각형의 개수를 구해야 합니다.

 

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

1. 전체 사각형의 개수를 계산합니다. (가로 길이 × 세로 길이)
2. 대각선에 의해 잘린 사각형의 개수를 계산합니다.
   1. 대각선이 지나가는 사각형의 개수는 가로 길이와 세로 길이의 최대공약수와 관련이 있습니다.
   2. 잘린 사각형의 개수 = 가로 길이 + 세로 길이 - 최대공약수
3. 전체 사각형의 개수에서 잘린 사각형의 개수를 빼서 사용할 수 있는 정사각형의 개수를 계산합니다.

 

이 문제에서는 최대공약수를 구하는 함수를 사용하여 가로 길이와 세로 길이의 최대공약수를 계산합니다. 최대공약수를 구하는 방법으로는 유클리드 호제법을 사용할 수 있습니다.

 

시도

1차 시도  (성공)

function solution(W, H) {
	// 최대공약수를 구하는 함수
	function gcd(a, b) {
		// b가 0이 될 때까지 반복
		while (b !== 0) {
			// a를 b로 나눈 나머지를 계산
			let r = a % b;
			// a에 b값을 할당
			a = b;
			// b에 나머지 r을 할당
			b = r;
		}
		// 최대공약수 반환
		return a;
	}

	// W와 H의 최대공약수 계산
	let g = gcd(W, H);

	// 전체 사각형 개수에서 대각선에 의해 잘린 사각형 개수를 뺌
	// 잘린 사각형 개수 = W + H - 최대공약수
	return W * H - (W + H - g);
}

이 코드에서는 최대공약수를 구하는 함수 gcd를 정의하고 있습니다. gcd 함수는 유클리드 호제법을 사용하여 두 수의 최대공약수를 계산합니다. 유클리드 호제법은 두 수 a와 b가 주어졌을 때, a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리를 이용합니다. 이 과정을 반복하여 나머지가 0이 될 때까지 계산하면 최대공약수를 구할 수 있습니다.

 

전체 사각형의 개수는 가로 길이 W와 세로 길이 H를 곱하여 계산합니다. 그리고 대각선에 의해 잘린 사각형의 개수는 W + H - 최대공약수로 계산할 수 있습니다. 최종적으로 전체 사각형의 개수에서 잘린 사각형의 개수를 빼서 사용할 수 있는 정사각형의 개수를 구합니다.

 

시간복잡도: O(log(min(W, H))) - 유클리드 호제법의 시간 복잡도

공간복잡도: O(1) - 추가적인 자료구조를 사용하지 않고 상수 개의 변수만 사용

 

2차 시도  (성공)

function solution(W, H) {
	// 최대공약수를 구하는 함수 (유클리드 호제법 사용)
	function gcd(a, b) {
		// b가 0이면 a가 최대공약수
		if (b === 0) return a;
		// b가 0이 아니면 재귀적으로 호출 (b와 a를 b로 나눈 나머지)
		return gcd(b, a % b);
	}

	// 전체 사각형 개수
	let totalSquares = W * H;

	// W와 H의 최대공약수 계산
	let greatestCommonDivisor = gcd(W, H);

	// 대각선에 의해 잘린 사각형 개수
	let cutSquares = W + H - greatestCommonDivisor;

	// 사용할 수 있는 사각형 개수 계산 및 반환
	return totalSquares - cutSquares;
}

2차 시도에서는 최대공약수를 구하는 함수 gcd를 재귀적으로 구현하였습니다. 유클리드 호제법을 사용하여 더 간결하게 최대공약수를 계산할 수 있습니다. 만약 두 수 중 하나가 0이라면 다른 수가 최대공약수가 됩니다. 그렇지 않은 경우에는 작은 수와 큰 수를 작은 수로 나눈 나머지를 인자로 하여 재귀적으로 gcd 함수를 호출합니다. 이 과정을 반복하면 최대공약수를 구할 수 있습니다.

 

전체 사각형 개수와 대각선에 의해 잘린 사각형 개수를 계산하는 부분은 1차 시도와 동일합니다. 최종적으로 전체 사각형 개수에서 잘린 사각형 개수를 빼서 사용할 수 있는 사각형 개수를 반환합니다.

 

시간복잡도: O(log(min(W, H))) - 유클리드 호제법의 시간 복잡도

공간복잡도: O(log(min(W, H))) - 재귀 호출로 인한 스택 사용