백준 1339 c++ "단어 수학" -PlusUltraCode-

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

 

[필자 사고]

처음 이 문제를 접할 때는 최상위 자릿수에서 최대의 값만 넣으면 될 줄 알았따.

그러나 실제로 모든 자릿수를 검증해야 된다. 중복되는 문자열이 있기 때문에

그래서 필자는 pow를 이용하여 실제로 문자열마다 자릿수의 값이 얼마인지 계산 후

가장 큰 값인 idx부터  9  8 7 6 등을 곱해 문제를 해결했다.

아래는 자세한 코드 해설이다.

[코드 해설]

구조 설명

1. 입력 받기 (Input)
   • N개의 단어를 입력받습니다.
   • arr라는 길이 26짜리 벡터를 만듭니다. (각각 알파벳 A~Z에 해당)
     • arr[0] → 'A'
     • arr[1] → 'B'
     • …
     • arr[25] → 'Z'
   • 각 단어를 입력받아 오른쪽 끝(1의 자리)부터 거꾸로 보면서,
     • 해당 알파벳에 자리수 값(1, 10, 100, 1000 등)을 더합니다.
     • → 즉, 알파벳별로 해당 알파벳이 차지하는 자릿수 가치 총합을 저장합니다.
2. 정렬하기 (Game_Start)
   • arr를 값이 큰 순서로 내림차순 정렬합니다.
     • 가치가 높은 알파벳부터 숫자 9, 8, 7, … 이런 식으로 배정하기 위해.
3. 숫자 배정하고 결과 계산
   • numbering = 9부터 시작해서,
   • 가치가 있는 알파벳(값이 0이 아닌 것) 순서대로
     • 현재 알파벳의 가치 × numbering 해서 resultSum에 더합니다.
     • 그리고 numbering을 1씩 줄여갑니다.
   • 마지막에 resultSum을 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

int N;
vector<int> arr;

bool cmp(int a, int b) {
	return a > b;
}

void Input() {

	cin >> N;
	arr.resize(26,0);

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		int pow = 1;
		for (int k = str.size()-1; k >=0; k--) {
			char ch = str[k];
			arr[ch - 'A'] += pow;
			pow*= 10;
		}
	}
}

void Game_Start() {
	sort(arr.begin(), arr.end(), cmp);

	int numbering = 9;
	int resultSum = 0;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == 0)continue;
		resultSum += arr[i] * numbering;;
		numbering--;
	}

	cout << resultSum;
}

int main(void) {
	Input();
	Game_Start();
}