완전탐색 > 모음사전 (Level 2)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

입출력 예

 

입출력 예 설명

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

 

소스코드

#include <string>
#include <map>
#include <vector>
#include <iostream>

using namespace std;

int solution( string word )
{
	int answer = 0;

	// 알파벳 순서
	map< char, int> words = { { 'A', 1 }, { 'E', 2 }, { 'I', 3 }, { 'O', 4 }, { 'U', 5 } };
	
	int count = words.size();
	vector < int > noc; // 각 자리수 경우의 수
	noc.assign( count + 1, 0 );

	for( int i = 1; i < count + 1; ++i )
		noc[ i ] = ( noc[ i - 1 ] * count ) + 1;

	for( int i = 0; i < word.size(); ++i )
	{
		char temp = word[ i ];
		map< char, int>::iterator iter = words.find( temp );

		if( iter == words.end() )
			return -1;

		answer += ( iter->second - 1 ) * noc[ count - i ] + 1;
	}

	return answer;
}

 

생각해 볼 다른사람 코드

using namespace std;

int solution( string word ) 
{
	int dp[ 6 ] = { 0,5 };
	string v = "AEIOU";
	int ans = word.size();

	for( int i = 2; i <= 5; ++i ) 
		dp[ i ] = 5 * ( dp[ i - 1 ] + 1 );

	for( int i = 0; i < word.size(); ++i ) 
	{
		int p = v.find( word[ i ] );
		if( p )
			ans += p * ( 1 + dp[ 4 - i ] );
	}

	return ans;
}

 

생각해 볼 것

노트를 피고 규칙을 찾아서 코딩화 했다. map을 사용해서 키 값으로 데이터 정리하는 것 까진 생각이 좋았지만, 다른 사람의 코드를 보니 일차원 적인 발상인 것 같다. 그리고 굳이 map을 안써도 string에서도 find 함수가 있다는 사실을 알게 됬다. string은 그저 char 형의 배열인 클래스인데 너무 문자열로만 받아들이는 것 같다.