[프로그래머스] JavaScript Lv2 - 모음 사전(84512)

개요

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

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 모음으로 이루어진 길이 5 이하의 모든 단어가 수록된 사전에서, 주어진 단어의 순서를 찾는 문제입니다. 이 문제를 해결하기 위해서는 사전에서 단어의 순서를 파악하는 것이 중요합니다.

문제 접근 방식은 다음과 같습니다.

1. 모음의 순서를 정의합니다. (예: A, E, I, O, U)
2. 주어진 단어의 각 글자를 모음 순서에 따라 변환합니다.
3. 변환된 값을 이용하여 사전에서의 순서를 계산합니다.

이 문제는 수학적 규칙을 찾아내는 것이 핵심입니다. 사전에서 단어의 순서는 다음과 같은 규칙을 따릅니다.

1. 첫 번째 글자는 1, 6, 31, 156, 781의 순서로 증가합니다. (5의 거듭제곱 - 1)
2. 두 번째 글자는 1, 5, 25, 125의 순서로 증가합니다. (5의 거듭제곱)
3. 세 번째 글자는 1, 5, 25의 순서로 증가합니다. (5의 거듭제곱)
4. 네 번째 글자는 1, 5의 순서로 증가합니다. (5의 거듭제곱)
5. 다섯 번째 글자는 1의 순서로 증가합니다. (5의 거듭제곱)

이 규칙을 이용하여 주어진 단어의 순서를 계산할 수 있습니다.

 

완전탐색 알고리즘

완전탐색 알고리즘(Brute Force Algorithm, 브루트 포스)은 가능한 모든 경우의 수를 전부 탐색하여 문제를 해결하는 알고리즘입니다. 이는 문제를 해결하는 가장 직관적이고 간단한 접근 방식 중 하나로, 모든 가능한 경우를 체계적으로 열거하고 각각의 경우를 검사하여 문제의 조건을 만족하는 해를 찾습니다.

 

완전탐색 알고리즘의 특징은 다음과 같습니다.

• 모든 경우의 수를 고려: 완전탐색은 문제의 조건을 만족하는 모든 가능한 해를 탐색합니다. 이는 문제의 크기가 작을 때 유용하지만, 문제의 크기가 커질수록 탐색 시간이 기하급수적으로 증가할 수 있습니다.
• 간단하고 직관적: 완전탐색은 문제를 해결하는 가장 직관적인 방법 중 하나입니다. 모든 가능한 경우를 체계적으로 검사하므로, 구현이 간단하고 이해하기 쉽습니다.
• 최적해 보장: 완전탐색은 모든 가능한 해를 탐색하므로, 항상 최적해를 찾을 수 있습니다. 즉, 문제의 조건을 만족하는 해 중에서 가장 좋은 해를 찾을 수 있습니다.
• 비효율적일 수 있음: 완전탐색은 모든 경우를 탐색하므로, 문제의 크기가 커질수록 탐색 시간이 기하급수적으로 증가할 수 있습니다. 이는 시간 복잡도 측면에서 비효율적일 수 있으며, 현실적인 시간 내에 해결하기 어려운 문제에는 적합하지 않을 수 있습니다.

 

완전탐색 알고리즘은 다음과 같은 상황에서 유용합니다.

• 문제의 크기가 작아서 모든 경우를 탐색해도 시간 안에 해결할 수 있는 경우
• 문제의 조건이 단순하고 경우의 수가 많지 않은 경우
• 최적해를 보장해야 하는 경우
• 다른 최적화 기법을 적용하기 전에 기본 해법으로 사용하는 경우

 

완전탐색 알고리즘의 예시로는 다음과 같은 것들이 있습니다.

• 순열과 조합 생성
• 부분 집합 생성
• 그리디 알고리즘에서의 모든 경우 탐색
• 백트래킹을 사용한 모든 경우 탐색
• 재귀 호출을 사용한 모든 경우 탐색

 

완전탐색은 문제를 해결하는 기본적인 접근 방식이지만, 효율성 측면에서는 최적이 아닐 수 있습니다. 따라서 문제의 조건과 제한사항을 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다. 완전탐색으로 해결할 수 없는 크기의 문제에는 다른 최적화 기법이나 근사 알고리즘을 적용해야 할 수 있습니다...!

 

즉, 요약하자면 완전탐색 알고리즘은 가능한 모든 경우의 수를 전부 탐색하여 문제를 해결하는 알고리즘입니다. 모든 가능한 해를 탐색하므로 최적해를 보장하며, 구현이 간단하고 직관적이고, 문제의 크기가 커질수록 탐색 시간이 기하급수적으로 증가하여 비효율적일 수 있습니다.

 

시도

1차 시도  (성공)

function solution(word) {
	const vowels = ["A", "E", "I", "O", "U"];
	let answer = 0;

	for (let i = 0; i < word.length; i++) {
		const index = vowels.indexOf(word[i]);
		answer += (index * (Math.pow(5, 5 - i) - 1)) / (5 - 1);
		answer++;
	}
	return answer;
}

이 코드는 수학적 규칙을 이용하여 단어의 순서를 계산합니다.

1. 모음의 순서를 정의합니다. (A, E, I, O, U)
2. 주어진 단어의 각 글자에 대해 다음을 수행합니다.
   1. 현재 글자의 모음 순서(index)를 구합니다.
   2. (index * (5^(5-i) - 1)) / 4를 answer에 더합니다. 이는 해당 자리에서 글자의 순서를 나타냅니다.
   3. answer에 1을 더합니다. 이는 해당 자리의 글자 자체의 순서를 나타냅니다.
3. 최종적으로 계산된 answer를 반환합니다.

시간 복잡도: O(word.length) - 단어의 길이에 비례하는 시간 복잡도를 가집니다.
공간 복잡도: O(1) - 상수 크기의 추가 공간만을 사용합니다.

 

2차 시도  (성공)

function solution(word) {
	const vowels = ["A", "E", "I", "O", "U"];
	const lengths = [781, 156, 31, 6, 1];

	let result = word.length;

	for (let i = 0; i < word.length; i++) {
		const index = vowels.indexOf(word[i]);
		result += lengths[i] * index;
	}

	return result;
}

이 코드는 1차 시도와 유사하지만, 각 자리에서의 순서를 미리 계산하여 배열(lengths)에 저장합니다.

1. 모음의 순서를 정의합니다. (A, E, I, O, U)
2. 각 자리에서의 순서를 미리 계산하여 lengths 배열에 저장합니다.
3. 주어진 단어의 길이를 result에 초기값으로 설정합니다. 이는 단어 자체의 길이를 나타냅니다.
4. 주어진 단어의 각 글자에 대해 다음을 수행합니다.
   1. 현재 글자의 모음 순서(index)를 구합니다.
   2. lengths[i] * index를 result에 더합니다. 이는 해당 자리에서 글자의 순서를 나타냅니다.
5. 최종적으로 계산된 result를 반환합니다.

시간 복잡도: O(word.length) - 단어의 길이에 비례하는 시간 복잡도를 가집니다.
공간 복잡도: O(1) - 상수 크기의 추가 공간만을 사용합니다.

 

3차 시도 (성공)

function solution(word) {
	// 생성된 모든 단어를 저장할 배열
	const dictionary = [];
	// 모음의 순서를 정의한 배열
	const vowels = ["A", "E", "I", "O", "U"];

	// 모든 가능한 단어를 생성하는 재귀 함수
	function generateWords(currentWord) {
		// 현재 단어의 길이가 5인 경우, 더 이상 단어를 생성하지 않고 종료
		if (currentWord.length === 5) {
			return;
		}

		// 모음의 각 글자에 대해 반복
		for (let i = 0; i < vowels.length; i++) {
			// 현재 단어에 모음 글자를 추가하여 새로운 단어 생성
			const newWord = currentWord + vowels[i];
			// 생성된 새로운 단어를 dictionary 배열에 추가
			dictionary.push(newWord);
			// 생성된 새로운 단어를 기반으로 generateWords 함수를 재귀적으로 호출
			generateWords(newWord);
		}
	}

	// generateWords 함수를 빈 문자열로 호출하여 모든 가능한 단어 생성
	generateWords("");

	// dictionary 배열에서 주어진 단어의 인덱스를 찾고, 1을 더한 값을 반환
	// 이는 사전에서의 순서를 나타냅니다.
	return dictionary.indexOf(word) + 1;
}

이 코드는 완전탐색 기법을 사용하여 모든 가능한 단어를 생성하고, 주어진 단어의 순서를 찾습니다.

1. dictionary 배열을 초기화합니다. 이 배열은 생성된 모든 단어를 저장할 것입니다.
2. vowels 배열을 정의합니다. 이 배열은 모음의 순서를 나타냅니다. ["A", "E", "I", "O", "U"]
3. generateWords 함수를 정의합니다. 이 함수는 재귀적으로 호출되어 모든 가능한 단어를 생성합니다.
   1. 함수는 currentWord라는 매개변수를 받습니다. 이는 현재 생성 중인 단어를 나타냅니다.
   2. 먼저, 현재 단어의 길이가 5인지 확인합니다. 길이가 5이면 더 이상 단어를 생성하지 않고 함수를 종료합니다.
   3. 모음의 각 글자에 대해 반복문을 실행합니다.
      1. 현재 단어에 모음 글자를 추가하여 새로운 단어(newWord)를 생성합니다.
      2. 생성된 새로운 단어를 dictionary 배열에 추가합니다.
      3. 생성된 새로운 단어를 기반으로 generateWords 함수를 재귀적으로 호출합니다. 이를 통해 새로운 단어에 모음을 추가하여 모든 가능한 조합을 생성합니다.
4. generateWords 함수를 빈 문자열("")로 호출합니다. 이는 처음부터 모든 가능한 단어를 생성하기 위함입니다.
5. dictionary 배열에서 주어진 단어(word)의 인덱스를 찾습니다. indexOf 메서드를 사용하여 단어의 인덱스를 얻고, 1을 더한 값을 반환합니다. 이는 사전에서의 순서를 나타냅니다.

기본적으로 모음의 모든 조합을 생성하여 사전 순서를 찾습니다. 이러한 방식은 단어의 길이가 길어질수록 생성해야 할 단어의 수가 기하급수적으로 증가하므로 효율성 측면에서는 최적이 아닐 수 있습니다. 다만, 단어(word)의 길이가 최대 5인지라 완전탐색으로도 충분할 여지가 많기는 합니다.

 

시간 복잡도: O(5^5) - 최대 5^5개의 단어를 생성하므로, 상수 시간 복잡도를 가집니다. (빈문자열도 계산할 때 고려하면 O(5^6)이 될 수도?)
공간 복잡도: O(5^5) - 최대 5^5개의 단어를 저장하므로, 상수 공간 복잡도를 가집니다.

 

주요 메서드

• indexOf(element): 배열에서 지정된 요소를 찾아 첫 번째로 나타나는 인덱스를 반환합니다. 요소가 배열에 없으면 -1을 반환합니다.
• Math.pow(base, exponent): 주어진 밑(base)을 주어진 지수(exponent)만큼 거듭제곱한 값을 반환합니다.
• push(element): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.

 

사족

개인적으로는 완전탐색으로 풀어야 한다는 게 발목을 잡았습니다. 다른 방법으로 쉽게 풀리는데 왜 이렇게 풀지라는 의문이 계속 남았는데... 어찌되었든 풀어냈습니다. 다만, 완전탐색이 그리 효율적인 방식이 아니라는 생각이 계속 드네요. 이러한 방식을 남용하면 안 될 것 같습니다.