[백준] 1339번: 단어 수학 (C언어)

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

난이도: solved.ac 골드 4

 

 

그리디 알고리즘 문제다

 

일단 알파벳을 담을 수 있는 26칸 짜리 배열을 선언한다

 

그리고 설명의 편의를 위해 이를 '알파벳 배열'이라고 하겠다

 

그리고 모든 값을 0으로 초기화 하는데, 나는 이 과정을 줄이기 위해 전역변수로 선언했다

 

그리고 단어를 입력받을 때

 

각 자리에 있는 알파벳을 해당 알파벳 배열에 저장하는데

 

우리가 십진수 231을 2*100+3*10+1*1로 나타내는 것처럼

 

단어를 십진수 수로 보고 각 자리에 맞는 weight를 곱하여 저장해준다

 

예를 들어, 단어 ABBDC는

 

A * 10000 + B * 1000 + B * 100 + D * 10 + C * 1

 

로 보고

 

A = 10000

B = 1000 + 100

C = 1

D = 10

을 저장한다

 

그러면 배열은 아래와 같이 된다

 

A	B	C	D	E	F	...
10000	1100	1	10	0	0	...

 

모든 단어를 알파벳 배열에 이렇게 저장한 후

 

위 배열을 수가 큰 것부터 정렬한 후

 

순서대로 9, 8, 7, 6, ...을 배정하여 곱해준다

 

그리고 이를 모두 합하면 원하는 답이 된다

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<math.h>

int character[26];

int compare(int* a, int* b) {
	return *b - *a;
}

int main() {
	int N, i, j;
	scanf("%d", &N);
	char word[9];
	int len, ch;	// len: 단어(word)의 길이, ch: 단어 내 알파벳
	int sum = 0;	// 수의 총합

	for (i = 0; i < N; i++) {
		scanf("%s", word);
		len = strlen(word);
		for (j = len - 1; j >= 0; j--) {
			ch = word[j] - 'A';
			character[ch] += pow(10, len - 1 - j);
		}
	}
	qsort(character, 26, sizeof(int), compare);
	for (i = 0; i < 10 ; i++)
		sum += character[i] * (9 - i);
	printf("%d", sum);
	return 0;
}