[프로그래머스] JavaScript Lv1 - 모의고사(42840)

개요

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

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 주어진 정답 배열과 각 수포자의 찍기 패턴을 비교하여 가장 많은 문제를 맞힌 사람을 찾는 완전탐색 알고리즘 문제입니다. 각 수포자의 찍기 패턴은 일정한 규칙을 가지고 반복되므로, 이를 활용하여 정답과 비교할 수 있습니다.

 

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

1. 각 수포자의 찍기 패턴을 배열로 정의합니다.
2. 정답 배열을 순회하면서 각 수포자의 찍기 패턴과 비교하여 맞힌 문제의 개수를 카운트합니다.
3. 가장 많은 문제를 맞힌 수포자를 찾아 해당 수포자의 번호를 결과 배열에 추가합니다.

이 문제에서는 배열 메서드 filter와 map, 그리고 spread 연산자(...)를 활용하여 코드를 간결하게 작성할 수 있습니다.

 

filter: 주어진 콜백 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환합니다.

map: 배열 내의 모든 요소에 대해 주어진 콜백 함수를 호출하고, 그 결과를 모아 새로운 배열을 반환합니다.

spread 연산자(...): 배열이나 객체를 펼쳐서 개별 요소로 분리합니다.

 

시도

1차 시도  (성공)

// 1차 시도 (성공)
function solution(answers) {
	const petterns = [
		[1, 2, 3, 4, 5],
		[2, 1, 2, 3, 2, 4, 2, 5],
		[3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
	];
	let score = [0, 0, 0];

	for (let i = 0; i < answers.length; i++) {
		for (let j = 0; j < petterns.length; j++) {
			if (petterns[j][i % petterns[j].length] === answers[i]) {
				score[j]++;
			}
		}
	}
	let max = Math.max(...score);
	let result = [];
	for (let i = 0; i < petterns.length; i++) {
		if (max === score[i]) {
			result.push(i + 1);
		}
	}
	return result;
}

1차 시도에서는 이중 for문을 사용하여 각 수포자의 찍기 패턴과 정답을 비교하고, 맞힌 문제의 개수를 score 배열에 저장했습니다. 이때 i % petterns[j].length를 사용하여 찍기 패턴을 반복적으로 적용했습니다.

그 다음 Math.max()와 spread 연산자를 사용하여 가장 높은 점수를 찾고, 해당 점수를 가진 수포자의 번호를 result 배열에 추가하여 반환했습니다.

이 방법은 직관적이고 이해하기 쉽지만, 이중 for문을 사용하므로 시간 복잡도는 O(n^2)입니다. 물론 두 번째 for문이 3번만 돌아가기에 O(n)으로 봐도 무방하기도 합니다. 공간 복잡도는 O(1)입니다.

 

2차 시도  (성공)

// 2차 시도 (성공) - 이게 아마도 가장 효율적?
function solution(answers) {
	let result = [];
	const petterns = [
		[1, 2, 3, 4, 5],
		[2, 1, 2, 3, 2, 4, 2, 5],
		[3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
	];
	let score = [0, 0, 0];

	for (let i = 0; i < answers.length; i++) {
		if (petterns[0][i % petterns[0].length] === answers[i]) score[0]++;
		if (petterns[1][i % petterns[1].length] === answers[i]) score[1]++;
		if (petterns[2][i % petterns[2].length] === answers[i]) score[2]++;
	}
	for (let i = 0; i < petterns.length; i++) {
		if (Math.max(...score) === score[i]) {
			result.push(i + 1);
		}
	}
	return result;
}

2차 시도에서는 이중 for문을 사용하지 않고, 각 수포자의 찍기 패턴을 한 번에 비교하도록 개선했습니다. 정답 배열을 순회하면서 각 수포자의 찍기 패턴과 정답을 비교하고, 맞힌 경우 해당 수포자의 점수를 증가시켰습니다.

마찬가지로 Math.max()와 spread 연산자를 사용하여 가장 높은 점수를 찾고, 해당 점수를 가진 수포자의 번호를 result 배열에 추가하여 반환했습니다.

이 방법은 이중 for문을 제거하여 시간 복잡도를 O(n)으로 개선했습니다. 다만 filter 및 map 같은 반복 메서드를 최소화하고, 기본적인 for문을 썼기에 다른 시도들에 비해서 미약하게나마 효율적이라고 할 수 있습니다. (기본 for문이 가장 빠름) 공간 복잡도는 여전히 O(1)입니다.

 

3차 시도 (성공)

// 3차 시도 (성공)
function solution(answers) {
	const patterns = [
		[1, 2, 3, 4, 5],
		[2, 1, 2, 3, 2, 4, 2, 5],
		[3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
	];

	const scores = patterns.map(
		(pattern) => answers.filter((answer, index) =>
			answer === pattern[index % pattern.length]).length
	);

	const maxScore = Math.max(...scores);

	return scores.map((score, index) => (score === maxScore ? index + 1 : null)).filter(Boolean);
}

3차 시도에서는 배열 메서드 filter와 map을 활용하여 코드를 더욱 간결하게 작성했습니다.

먼저 patterns.map()을 사용하여 각 수포자의 점수를 계산했습니다. 내부적으로 answers.filter()를 사용하여 정답과 일치하는 문제의 개수를 세었습니다. filter 메서드의 콜백 함수에서는 현재 정답(answer)과 찍기 패턴에서 해당 인덱스에 해당하는 값(pattern[index % pattern.length])을 비교하여 일치하는 경우만 필터링했습니다. 필터링된 배열의 길이가 곧 맞힌 문제의 개수가 됩니다.

그 다음 Math.max()와 spread 연산자를 사용하여 가장 높은 점수(maxScore)를 찾았습니다. 마지막으로 scores.map()을 사용하여 각 점수를 maxScore와 비교하고, 일치하는 경우 해당 수포자의 번호를, 일치하지 않는 경우 null을 반환하도록 했습니다. 그리고 filter(Boolean)을 사용하여 null이 아닌 값만 필터링하여 최종 결과를 반환합니다.

시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)입니다.

 

4차 시도 (성공)

// 4차 시도 (성공)
function solution(answers) {
	var answer = [];
	var a1 = [1, 2, 3, 4, 5];
	var a2 = [2, 1, 2, 3, 2, 4, 2, 5];
	var a3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

	var a1c = answers.filter((a, i) => a === a1[i % a1.length]).length;
	var a2c = answers.filter((a, i) => a === a2[i % a2.length]).length;
	var a3c = answers.filter((a, i) => a === a3[i % a3.length]).length;
	var max = Math.max(a1c, a2c, a3c);

	if (a1c === max) {
		answer.push(1);
	}
	if (a2c === max) {
		answer.push(2);
	}
	if (a3c === max) {
		answer.push(3);
	}

	return answer;
}

5차 시도에서는 각 수포자의 찍기 패턴을 개별 변수로 정의하고, filter 메서드를 사용하여 각 수포자의 점수를 계산했습니다. 그리고 Math.max()를 사용하여 가장 높은 점수를 찾고, 해당 점수를 가진 수포자의 번호를 answer 배열에 추가하여 반환했습니다.

이 방법은 각 수포자의 점수를 개별적으로 계산하고 비교하여 결과를 도출하는 직관적인 접근 방식입니다. 시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)입니다.

 

사족

이 문제를 통해 배열 메서드의 활용과 알고리즘 설계에 대해 배울 수 있었습니다. 초기에는 이중 for문을 사용하여 문제를 해결했지만, 점차 배열 메서드를 활용하여 코드를 간결하고 효율적으로 개선해 나갔습니다.

특히 filter와 map 메서드를 적극 활용하여 코드의 가독성을 높이고, 불필요한 반복문을 제거할 수 있었습니다. 개인적으로는 앞으로도 filter와 map 메서드에 대한 공부가 갈수록 더 중요해질 것 같은 느낌입니다.