백준 BOJ 1339 - 단어수학

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

1339번: 단어 수학

정올같은데에서 본거같은 문제이다.

 

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm> 

char arr[11][10];
int table[128] = {0}; // 문자 - 숫자 대응 배열.

int main(){
	int n,tmp,sum=9,ans=0;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%s", &arr[i]);
		tmp = strlen(arr[i]);
		for(int j=0; j<tmp; j++){
			table[arr[i][j]] += pow(10, tmp-j-1);
		}
	}
	
	std::sort(table, table + 128);
	for(int i=127; i>=0; i--){
		if(table[i] == 0) continue;
		ans += table[i] * sum;
		sum--;
	}
	printf("%d", ans);
}

arr변수에다 입력을 받고

tmp에다 문자열의 길이를 저장한다.

strlen()을 쓸때 시간복잡도가 O(N)꼴이기 때문에 이렇게 따로 변수로 빼주는게 좋다.

​

각 글자에 대한 포문을 한번 더 돌려서,

table에 들어간 횟수를 넣어주는데, 여기서 중요한점은

어느 자리에서 몇번사용됬는지를 표현해주기위해

pow(10, tmp-j-1)을 더해주었다는 것이다.

문자열의 길이가 길 수록 가장 앞 글자의 크기는 커지는데,

단순히 A가 나온 횟수만을 기록해버리면

BAAAAA와 같은 문장이 들어왔을때 제대로 결과를 출력하지못하고 899999라는 잘못된 값을 반환하기 때문이다.

따라서 pow(10, tmp-j-1)을 더해줘서

BAAAAA같은 문장의 경우

B에 100000, A에 11111으로 그 우선순위를 명확히 해주었다.

​

그다음에는 정렬시켜준 다음, 각 문자에 숫자를 할당해준다.

BAAAAA의 경우

B에 9가 할당되 900000가 ans에 더해지고,

그 다음 A에 8이 할당되어 88888이 ans에 더해질 것이다.

​

​