[C언어] 단어 수학 (백준 1339번)-pow, Quic sort 사용

정말 오랜만에 백준을 풀어보았다..

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

1339번: 단어 수학

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

---

풀이

우선 규칙성을 찾아보자면 예시 문제에서 알 수 있다시피 가장 큰 자릿수에 있는(만의 자리) A에 가장 큰 수인 9를, 그 다음 자리에 8을... 이 순서대로 넣어야 최댓값을 얻을  수 있다. 
그런데 만약 ABCE + EBCA + EAB 처럼 A와 E가 둘다 가장 큰 자리에 있을 땐, 다음 자릿수를 보고 E가 100의 자리에, A는 10의 자리에 있기 때문에 E가 더 커야함을 판단할 수 있다.

ABCE + EBCA + EAB

8769 + 9786 + 987 = 19542

즉, 알파벳이 있는 자릿수를 고려하여 문제를 해결하는 방식으로 접근했다.

단어 ABC를 반복문으로 인덱스를 탐색하면서 A가 나오면 100의 자리임을, B가 나오면 10, C는 1을 각각 저장해준다.

 

1. 배열 만들기

int N;

char word[9];

int alpha[26] = {0};

일단 단어의 개수를 받아오기 위한 변수 N,
단어는 최대 길이가 8이므로 문자열의 마지막 인덱스에 끝을 의미하는 널문자 '\0' 가 들어가는 것을 고려해 길이 + 1로 만들어주고,

모든 알파벳의 숫자가 동일해야 하니까 26의 길이를 가진 전체 알파벳 배열을 만들어준다.

 

2. 단어 개수, 단어 입력 받기

scanf("%d", &N);

for (i = 0; i < N; i++) { // 모든 단어들

  scanf("%s", word);

}

테스트 케이스를 입력 받기 위해 scanf를 사용한다.

단어(테스트 케이스)의 개수만큼 반복문을 돌며 각 단어를 입력 받는다.

배열도 포인터처럼 주소를 담고 있으므로 배열 이름 앞에는 &을 붙이지 않아도 된다.

 

3. 단어마다 각 알파벳의 자릿수 파악하기(pow 함수)

for (i = 0; i < N; i++) { // 모든 단어들

  scanf("%s", word);

 

  len = strlen(word);

  for (j = 0; j < len; j++) { // 각 단어별로

    alpha[word[j] - 'A'] += pow(10, len - 1 - j); // 자릿수 저장

  }

}

반복문 내부에서 받아온 단어의 각 알파벳마다 자릿수를 파악해야 하므로 단어의 길이만큼 반복문을 돌아준다.

 

길이를 strlen()을 이용해 변수에 저장.(#include <string.h> 라이브러리를 추가해줘야 쓸 수 있다)

단어가 ABC면 strlen('ABC') == 3

 

알파벳이 문자열 형태이기 때문에 아스키코드 'A'(65)를 빼서 인덱스로 사용한다.

A - 'A' 는 0번째 인덱스, B - 'A' 는 1번째···

이제  알파벳이 A(ABC에서) 이면 배열의 0번째 자리에 100을 저장 해야하고, B는 1번째 인덱스에 10, C는 2번째 인덱스에 1을 저장해줘야 한다.

 

자릿수를 10의 제곱으로 표현하기 위해 pow 함수를 이용했다.(power function, 거듭제곱)

기본 형식은 아래와 같다.

#include <math.h>

double pow(double x, double y);

x의 y 제곱을 리턴해준다.

 

이 방식으로 ABC의 자리수를 저장하면 배열은

0: A  1: B   2: C

[100,  10,  1 ···]

이 배열에 다음 단어의 자릿수를 계속 더하면(가중치를 주면) 큰 자릿수를 가지는 알파벳을 알 수 있고, 큰 값이 들어있는 알파벳부터 9, 8, 7··· 이렇게 대응된다고 볼 수 있다.

 

4. 가장 큰 자릿수부터 숫자와 대응시키기

int compare(const void * a, const void *b) {

  return *(int *)b - *(int *)a;

}

//정렬

qsort(alpha, 26, sizeof(int), compare);

 

int result = 0;

for (i = 0; i < 10; i++) {

  result += alpha[i] * (9 - i);

}

  printf("%d", result);

큰 숫자부터 쓰기위해서 최댓값을 찾아도 되고 하지만 간단하게 알파벳 배열을 정렬해주었다.

qsort함수를 이용했고(퀵 정렬), <stdlib.h>를 추가해 쓸 수 있다.

비교함수를 이용해 오름차순, 내림차순 정렬이 가능하고 아래 요소들이 들어간다.

qsort(정렬 할 배열, 요소 개수, 요소 크기, 비교 함수);

요소 크기는 자료형의 메모리 공간 크기를 sizeof()로 넣어줄 수 있다. 비교 함수는 괄호를 붙이지 않은 포인터 함수를 넣어준다.

매개변수 void *는 타입에 상관없이 포인터를 받을 수 있다는 뜻이다.

compare함수에서 정수형 포인터 a와 b를 받아오고, 

만약 오름차순이면 return *(int *)a - *(int *)b;을 해주면
배열이 [5, 4]이면 5- 4 = 1 양수이므로 위치를 바꿔준다. -> [4, 5]

반대로 내림차순이면 b - a가 양수면 더 큰 b가 앞에 위치하게 된다.

자릿수의 합이 가장 큰 알파벳에 9부터 곱해줄 것이기 때문에 내림차순으로 비교 함수를 작성해준다.

 

마지막으로 값을 저장할 result변수를 만들어 정렬된 알파벳에 9 - i 로 숫자를 점점 줄여가며 9~0까지 숫자를 대입한 결과를 얻을 수 있다.

전체 코드

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int compare(const void * a, const void *b);

int main(void) {
	int N;
	char word[9];
	int alpha[26] = {0};
	int i, j, len, result = 0;

	scanf("%d", &N);

	for (i = 0; i < N; i++) { // 모든 단어들
		scanf("%s", word);
		len = strlen(word);
		for (j = 0; j < len; j++) { // 각 단어별로
			alpha[word[j] - 'A'] += pow(10, len - 1 - j); // 자릿수 저장
		}
	}
	//정렬
	qsort(alpha, 26, sizeof(int), compare);

	for (i = 0; i < 10; i++) {
		result += alpha[i] * (9 - i);
	}
		printf("%d", result);
}

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

 

참고

퀵 정렬 함수 사용하기: https://dojang.io/mod/page/view.php?id=2028

pow: https://www.ibm.com/docs/ko/i/7.3?topic=functions-pow-compute-power