Word Index

알고리즘 2010.07.31 00:58 |

문제 요약 : 어떤 string이 숫자 값을 갖게 됩니다. string의 길이는 1~5이고, 뒤에 나오는 문자가 앞의 문자보다 커야만 합니다.
그렇지 않을 경우에는 invalid하다고 하여 0을 출력합니다.

예를 들면, 
a = 1
b = 2
c = 3
...
z = 26
ab = 27
aa는 invalid이므로 0
...
vwxyz = 83681

입력으로 스트링이 들어오면, 그 스트링에 해당하는 숫자를 반환하면 됩니다.

문제 링크





해결 방법 : 경우의 수를 따져가며 대표 string의 테이블을 구성했습니다. 
대표 string은 1자리 문자열일 경우 a, b, c, ,.... , z까지 모두 되고,
2자리 문자열일 경우 ab, bc, cd, de, .... , yz 가 됩니다. 
3자리 문자열일 경우 abc, bcd, cde, def, ... xyz가 됩니다.
이렇게 대표 문자열의 숫자 값을 테이블에 넣어두고, 계산을 진행합니다.

이 대표 문자열은 테이블에 다음과 같이 대응시켰습니다.

a = table[a][1]
b = table[b][1]
...
z = table[z][1]
ab = table[a][2]
bc = table[b][2]
...
yz = table[y][2]
abc = table[a][3]

즉, 이중 배열 table[][]이 있는데, 첫번째 대괄호 안에는 대표 문자의 시작 문자가 들어가고, 두번째 대괄호에는 문자열의 자리수가 들어갑니다.

그리고 그 값을 구할 때에는 테이블에서 약간의 규칙을 찾아야하는데, 경우의 수를 조금 생각해야할 것 같군요.
그리고 테이블의 값을 구하는 순서는 1자리 문자열부터 a~z까지 차례대로 구하고, 그 다음에 2자리 문자열 a~y까지 구하는 방식으로 합니다.(2자리 문자열은 yz가 마지막이므로 z는 구할 필요가 없습니다.) 

그러면 예를 들어 ab까지 즉, table[a][2]까지 구해진 상태에서 bc (table[b][2])를 구하려고 해봅시다.
bc의 값은 일단 ab의 값에서 출발해야 합니다. 왜냐하면 ab -> ac -> ad -> ... -> bc가 되기 때문이죠.
bc를 구하기 전에 az를 먼저 구해봅시다. az는 ab의 값에서 z의 값을 더하고 b의 값을 뺀 것과 같습니다.(왜 그런지는 직접 손으로 테이블 그려서 해보세요^^)
그렇게 az를 구하면 bc는 az의 바로 다음 문자열이라는 것을 깨닫게 됩니다.

즉, table[b][2] = table[a][2] + table[z][1] - table[b][1] + 1 이 됩니다.

이 식을 조금더 일반화 해보면, 

table[j][i] = table[j - 1][i] + table['z' - i + 1][i - 1] - table[j][i - 1] + 1;

이 됩니다.
위 식에서 table['z' - i + 1][i - 1]이 되는 것은, 1자리에서는 z까지 계산하지만, 2자리에서는 y까지 계산하고, 3자리에서는 x까지 계산하는 것과 관계가 있습니다.

이런 부분은 글로 적는 것보다 직접 테이블을 그려서 이해하는게 더 나을거라 생각이 드네요.


이런 방법으로 테이블을 구성하면 문제의 80% 정도는 푼거라 생각이 듭니다.

이제는 이미 구성된 테이블을 이용해서 문자열의 숫자만 계산해내면 되는거죠. ㅎ
예를 들어서 바로 설명하겠습니다.

만약, ace의 값을 구하고자 한다하면,
ace는 일단 테이블의 abc 값에서 시작합니다.
그리고 여기에서 bc의 값을 빼고 cd의 값을 더합니다.
또 여기에서 d의 값을 빼고 e의 값을 더합니다.

다시 식으로 정리를 해보면
ace = +abc - bc + cd - d + e
가 됩니다.

대충 감이 오시나요?
일단 위 식에서 사용한 값들은 모두 테이블에 저장되어 있는 대표값들 입니다.
그리고 abc에서 bc를 빼준 뒤 cd로 가는 것은, abc에서 acd 의 값으로 가기 위해서 입니다.
그리고 여기에서 d를 빼준 뒤 e를 더하는 것이 acd에서 ace가 되는 길이죠.

결과 : Accepted

이쯤에서 소스 코드를 보여드리겠습니다.

#include<iostream>
#include<string>

using namespace std;

int table['z' + 2][6];

void makeTable() {
	//테이블은 단 1회 만든다.
	//init
	memset(table, 0, sizeof(table));

	//process
	for(int i = 1; i <= 5; i++) {
		int c = 'z' - i + 2;
		int iterSize = c - 1;
		int addingNumber = table[c][i - 1];

		for(int j = 'a'; j <= iterSize; j++) {
			table[j][i] = table[j - 1][i] + addingNumber + 1 - table[j][i - 1];
		}
		table['a' - 1][i + 1] = table['a'][i];
	}
}

bool isNotValid(string str) {
	int size = str.length();
	for(int i = 0; i < size - 1; i++) {
		if(str[i] >= str[i + 1]) return true;
	}
	
	return false;
}

int getNumber(string str) {
	int sum = 0;
	int size = str.length();
	int digit = size;

	for(int i = 0; i < size; i++) {
		char c = str[i];
		sum += table[c][digit] - table[c + 1][digit - 1];
		digit--;
	}

	return sum;
}

int main() {
//	freopen("input.txt", "r", stdin);

	makeTable();

	string str;
	while(cin >> str) {
		if(isNotValid(str)) 
			cout << 0 << endl;
		else 
			cout << getNumber(str) << endl;
	}
	return 0;
}




글로 적으려니 정말 힘들군요..
어쨌든 이러한 방법으로 문제를 풀 수 있었습니다.
더 좋은 방법이 있다면 피드백 부탁드립니다.^^
저작자 표시
신고

'알고리즘' 카테고리의 다른 글

Prime Gap  (0) 2010.08.28
Palindrome Numbers  (2) 2010.08.05
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29
Posted by Code-Moon

댓글을 달아 주세요

티스토리 툴바