[프로그래머스] JavaScript Lv1 - 체육복(42862)

개요

문제 이름: 체육복 (42862)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42862
플랫폼: 프로그래머스
알고리즘 분류: 탐욕법(Greedy)
소요 시간: 30분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 탐욕법(Greedy, 그리디) 알고리즘을 사용하여야 합니다. 탐욕법 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 방식으로, 문제를 단계별로 해결해 나가는 알고리즘입니다.

 

문제에서 요구하는 사항은 다음과 같은 상황입니다.

1. 전체 학생 수 n명 중에서 체육복을 도난당한 학생들의 번호가 lost 배열에, 여벌 체육복을 가져온 학생들의 번호가 reserve 배열에 주어집니다.
2. 체육복을 빌려줄 때는 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 빌려줄 수 있습니다.
3. 체육수업을 들을 수 있는 학생의 최대값을 구해야 합니다.

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

1. 각 학생이 가진 체육복의 개수를 저장할 배열을 생성합니다. 초기에는 모든 학생이 1개의 체육복을 가지고 있다고 가정합니다.
2. 여벌 체육복을 가져온 학생들의 체육복 개수를 1 증가시킵니다.
3. 체육복을 도난당한 학생들의 체육복 개수를 1 감소시킵니다.
4. 체육복이 없는 학생(개수가 0인 학생)을 찾아 앞번호 학생이나 뒷번호 학생에게 체육복을 빌릴 수 있는지 확인합니다.
   • 앞번호 학생이 여벌 체육복을 가지고 있다면(개수가 2라면), 현재 학생에게 체육복을 빌려주고 앞번호 학생의 체육복 개수를 1 감소시킵니다.
   • 앞번호 학생에게 빌리지 못했다면, 뒷번호 학생이 여벌 체육복을 가지고 있는지 확인하고, 있다면 현재 학생에게 체육복을 빌려주고 뒷번호 학생의 체육복 개수를 1 감소시킵니다.
5. 최종적으로 체육복 개수가 1 이상인 학생의 수를 계산하여 반환합니다.

이를 통해 최대한 많은 학생이 체육수업을 들을 수 있도록 체육복을 적절히 빌려주는 것이 가능합니다.

 

시도

1차 시도  (성공)

// 1차 시도 (성공)
function solution(n, lost, reserve) {
	let result = 0;
	let arr = new Array(n).fill(1);
	for (let i = 0; i < lost.length; i++) {
		arr[lost[i] - 1]--;
	}
	for (let i = 0; i < reserve.length; i++) {
		arr[reserve[i] - 1]++;
	}
	for (let i = 0; i < n; i++) {
		if (arr[i] === 0) {
			if (arr[i - 1] === 2 && i > 0) {
				arr[i]++;
				arr[i - 1]--;
			} else if (arr[i + 1] === 2 && i < n - 1) {
				arr[i]++;
				arr[i + 1]--;
			}
		}
		if (arr[i] > 0) {
			result++;
		}
	}
	return result;
}

1차 시도에서는 앞서 위에서 설명한 접근 방식을 그대로 구현했습니다.

먼저 arr 배열을 생성하여 모든 학생의 체육복 개수를 1로 초기화합니다. 그리고 lost 배열을 순회하면서 해당 학생의 체육복 개수를 1 감소시키고, reserve 배열을 순회하면서 해당 학생의 체육복 개수를 1 증가시킵니다.

그 다음 arr 배열을 순회하면서 체육복이 없는 학생(개수가 0인 학생)을 찾습니다. 해당 학생의 앞번호 학생이 여벌 체육복을 가지고 있다면(개수가 2라면), 현재 학생에게 체육복을 빌려주고 앞번호 학생의 체육복 개수를 1 감소시킵니다.

 

앞번호 학생에게 빌리지 못했다면, 뒷번호 학생이 여벌 체육복을 가지고 있는지 확인하고, 있다면 현재 학생에게 체육복을 빌려주고 뒷번호 학생의 체육복 개수를 1 감소시킵니다.

마지막으로 arr 배열을 순회하면서 체육복 개수가 1 이상인 학생의 수를 result에 누적하여 반환합니다.

이 방법은 배열을 사용하여 각 학생의 체육복 개수를 관리하고, 체육복이 없는 학생을 찾아 앞뒤 학생에게 체육복을 빌리는 과정을 구현한 것입니다.

 

시간 복잡도는 O(n)이며, 공간 복잡도 또한 O(n)입니다.

 

2차 시도  (성공)

// 2차 시도 (성공)
function solution(n, lost, reserve) {
	let arr = new Array(n).fill(1);
	lost.forEach((element) => arr[element - 1]--);
	reserve.forEach((element) => arr[element - 1]++);

	for (let i = 0; i < n; i++) {
		if (arr[i] === 0) {
			if (arr[i - 1] === 2) {
				arr[i]++;
				arr[i - 1]--;
			} else if (arr[i + 1] === 2) {
				arr[i]++;
				arr[i + 1]--;
			}
		}
	}
	return arr.filter((value) => value > 0).length;
}

2차 시도에서는 1차 시도와 유사한 접근 방식을 사용하였지만, 코드를 더욱 간결하게 작성하였습니다.

 

lost 배열과 reserve 배열을 순회하면서 체육복 개수를 감소시키고 증가시키는 부분을 forEach 메서드를 사용하여 간단히 처리하였습니다. forEach 메서드는 배열의 각 요소에 대해 주어진 함수를 실행합니다.

 

체육복이 없는 학생을 찾아 앞뒤 학생에게 체육복을 빌리는 과정은 1차 시도와 동일합니다. 다만 앞번호 학생이 존재하는지 확인하는 조건문(i > 0)과 뒷번호 학생이 존재하는지 확인하는 조건문(i < n - 1)을 제거하였습니다. 이는 해당 조건문이 없어도 배열의 인덱스 범위를 벗어나는 경우 undefined로 처리되기 때문에 문제가 되지 않습니다.

 

마지막으로 filter 메서드를 사용하여 체육복 개수가 1 이상인 학생의 수를 계산하여 반환합니다. filter 메서드는 주어진 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환합니다.

이 방법은 1차 시도와 동일한 시간 복잡도(O(n))와 공간 복잡도(O(n))를 가집니다. 하지만 코드의 가독성과 간결성이 이전보다 향상되었습니다.

 

3차 시도 (성공)

// 3차 시도 (성공)
function solution(n, lost, reserve) {
	const arr = new Array(n).fill(1);

	for (const value of reserve) {
		arr[value - 1]++;
	}

	for (const value of lost) {
		arr[value - 1]--;
	}

	for (let i = 0; i < n; i++) {
		if (arr[i] === 0) {
			if (arr[i - 1] === 2) {
				arr[i]++;
				arr[i - 1]--;
			} else if (arr[i + 1] === 2) {
				arr[i]++;
				arr[i + 1]--;
			}
		}
	}

	return arr.filter((count) => count > 0).length;
}

3차 시도에서는 2차 시도와 유사한 접근 방식을 사용하였지만, forEach 메서드 대신 for...of 루프를 사용하여 배열을 순회했습니다. for...of 루프는 배열의 각 요소를 순회하며, 요소의 값을 변수에 할당합니다.

 

reserve 배열을 순회하면서 해당 학생의 체육복 개수를 1 증가시키고, lost 배열을 순회하면서 해당 학생의 체육복 개수를 1 감소시킵니다.

 

체육복이 없는 학생을 찾아 앞뒤 학생에게 체육복을 빌리는 과정은 이전 시도와 동일합니다. 마지막으로 filter 메서드를 사용하여 체육복 개수가 1 이상인 학생의 수를 계산하여 반환합니다.

 

이 방법 역시 이전 시도와 동일한 시간 복잡도(O(n))와 공간 복잡도(O(n))를 가지며, for...of 루프를 사용하여 코드의 가독성을 유지하면서도 간결하게 작성되었습니다.

 

사족

이번 문제 해결을 통해 탐욕법(그리디) 알고리즘에 대해 알 수 있었습니다. 또한, 배열 메서드인 forEach와 filter를 사용하여 코드를 간결하고 가독성 있게 작성하는 방법도 배울 수 있었습니다.

특히 for...of 루프를 사용하여 배열을 순회하는 방식은 코드의 가독성을 유지하면서도 간결하게 작성할 수 있는 유용한 방법이라는 것을 알게 되었습니다. 앞으로도 많이 사용할 것 같습니다.