[백준: 1339] 단어 수학 (발표자료)

들어가며

수업시간에 알고리즘 문제 발표를 맡게 되어 이 글을 작성한다.

 

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

단어 수학

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

35715

16563

12685

46.047%

문제

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

단어 수학 문제는 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, B, C, D~~ 등등의 알파벳으로 조합된 단어가 입력되고 각각을 함수라고 칭하자. 이때 1~9 의 숫자를 A = 9, B = 8, C = 7, D = 6 과 같이 중복없이 할당하여 가장 높은 값을 만드는 것이 이문제의 핵심이다.  언듯 보면 "에이 그냥 맨첨에 나오는 문자열에 9에서 아래로 순서대로 할당하면 되잖아~"라고 생각이 들만큼 간단한것 같지만. 입력하는 단어가 한개가 아닌 두개 이상이 입력되어 나온 다는 것이다. 벌써부터 풀기 싫죠? 

예제를 들어 설명해드리겠습니다.

 

- 1번 예제 

입력

2
AAA
AAA

출력

1998

 

위의 입력을 보면 A 밖에 없다. 그러니 A에 할당할 수 있는 가장 큰 수는 9. 그럼 A를 숫자 9로 치환하면 999 + 999 = 1998가 되어 출력이 1998로 나오는 거 ㅇㅇ

 

-2번 예제

입력 2

2
GCF
ACDEB

출력 2

99437

 

우선 고려 해야될 것. 이제는 난잡하다. 우선 가장 큰 수는 ACDEB로 GCF보다  자릿수가 높은 A와 C는 무조건 순차적으로 가장 높은수 A = 9, C = 8이 할당되어야 한다. 그리고 나머지 셋째자릿수인 D, G는 똑같이 한개밖에 없으니 7, 6이 둘중에 아무거나 할당되면 된다. 그럼 D = 7, G = 6으로 가정.  그럼 둘째자릿수인 E와 C를 보면 C는 이미 앞에서 8로 할당이 되었기에 E = 5를 할당. 나머지 B, F는 4와 3을 아무거나 할당하면 되기에 B = 4, f = 3을 가정. 이렇게 

G C F
6 8 3

A C D E B
9 8 7 5 4

 이를 더하면 98754 + 683 = 99437이 나오게 된다. 

 

그럼 이 점들을 주의하면서 코드를 짜보자. 

 

1번째 시도

처음시도에는 그냥 알파벳 중에서 많이 나온 것을 기준으로 index에다가 순차적으로 값을 체크해서 가장 큰 것 순서대로 값을 부여하자고 생각하였다. 하지만 코드를 작성하는 도중 "아 씨 이러면 가장 많이 나온 숫자가 가장 높은 숫자가 아니여도 우선 순위가 부여되어 가장 높은 값이 할당될 수 있잖아?!" 라는 생각으로 작성하다가 잘못됨을 감지 후 리셋.

2번째 시도

이번에는 처음 시도를 바탕으로 그럼 2중 백터로 크기 순서대로 나열하면 어떨까~ 해서 2중 백터로 큰것 대로 나열을 해도 나오는 것에 따라 우선순위가 바뀔 수 있다는 것을 인지.. 아효...

3번째 시도

번호를 1~2번 시도와 같이 크기별로 우선순위를 매기는 것이 아니라 각각의 단어에 우선순위를 넣어서 비교해야되고 그렇게 되면 이전 vector를 다시 끄집어 내서 비교할 필요도 뭣도 없다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> v;

int index[26];

bool compare(pair<int, string> a, pair<int, string> b) {

	return a.first > b.first;
}

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

int main() {
  string enNumber;
  string enIdx;
  int num = 0;
  int n;
  
  cin >> n;

  for(int i = 0; i < n; i++) {
    cin >> enNumber;
    v.push_back(enNumber);
  }

  auto it = v.begin();

  int i = 0;

  while(it != v.end()) {
    enIdx = *it;

    num = 1;
    for(int i = it -> length() - 1; i >= 0; i--) {
      index[enIdx[i] - 'A'] += num;
      num *= 10;
    }
    i++;
    it++;
  }

  sort(index, index + 26, compare1);

  int allNum = 0;
  int cntNum = 9;

  for (int i = 0; i < 26;i++) {
		if(cntNum == 0) {
      break;
    }
		allNum += index[i] * cntNum--; 
	}

  cout << allNum;

  return 0;
}

/*
const auto&:
  const: 불변
  auto&: 원본 데이터를 참조합니다. 복사본을 만들지 않고 직접 원본을 사용하므로 메모리 사용을 절약하고 성능을 향상시킵니다.

auto:
  단순히 auto를 사용하면 데이터가 복사됩니다. 큰 데이터 구조에서는 메모리와 성능 면에서 비효율적일 수 있습니다.
*/

로 제출하면 

 

 

짜라잔 ~