[백준/Baekjoon] 1339 단어 수학 C++ :: Greedy

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

1339번: 단어 수학

---

1. Logic

처음 생각은 긴 문자열부터 첫번째 짜리부터 순서대로 9, 8, 7 이렇게 큰 숫자부터 넣어주면 된다고 생각했지만 문자가 중복되게 나오는 경우의 수도 있기 때문에 고려를 해주어야 한다.

 

예를 들어 

ABC

BCA

같은 경우가 대표적인데, 이때는 A와 B중 어느 알파벳에 9를 할당해 줄 지 구해야 한다.

각 자릿수에 가능한 숫자를 구해보면

A=100 B=10 C=1 > 100A 10B 1C

B=100 C=10 A=1 > 100B 10C 1A

이기 때문에 

A의 합은 101A

B의 합은 110B

C의 합은 11C

그러므로 B>A>C의 순서대로 9부터 큰 숫자를 부여해주면 된다. 

 

문제에서 주어진 두번째 테스트케이스 또한 구해보자면

100G 10C 1F

10000A 1000C 100D 10E 1B

순서대로 나열하면 

10000A > 9

1010C > 8

100G 100D >7 | 6

10E > 5

1F 1B > 4 | 3

이중 G와 D, F와 B는 우선순위가 똑같기 때문에 둘중 어떤 수를 줘도 상관이 없다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int alpha[26];

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;

        int pow = 1;
        //1의 자리부터 각 자릿수 계산
        for(int j = str.size() - 1; j >= 0; j--) {
            //각 알파벳 별 가중치
            alpha[str[j] - 'A'] += pow;
            pow *= 10;
        }
    }

    //내림차순 정렬 > 큰 숫자부터 계산
    sort(alpha, alpha + 26, cmp);

    int num = 9;
    int answer = 0;

    for(int i = 0; i < 26; i++) {
        if(alpha[i] == 0) break;
        answer += alpha[i] * num--;
    }
    cout << answer;
}

 

 

---

 

 

3. Feedback

대충 감이 왔는데 아이디어 떠올리기가 힘들었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90