[G3] 백준 1132번 합 C++ 그리디 알고리즘, 정렬

리뷰

 

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

그렇게 어려운 문제라고 생각하지 않고 접근했는데 0으로 시작하는 수는 없다는 조건때문에 괘나 헤맸다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• w : 각 문자의 가중치를 저장할 배열
• f : 각 문자가 맨 앞에 나온적이 있는지를 저장할 배열
• v : 실제로 해당 숫자가 나왔는지 여부를 저장할 배열
• n : 문자열의 개수를 저장할 변수
• val : 문자에 할당된 값을 저장할 변수
• words : 문자열을 저장할 배열

 

함수

1. cmp

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

 

sort함수에 할당할 비교 함수, w값이 높은 순서대로 정렬한다.

 

 

문제풀이

1. n값을 입력 받고, n개의 문자열을 입력 받아 words배열을 초기화한다.
2. n개의 문자열을 순회하며 첫번째로 나온 문자를 f배열의 값을 true로 저장한다.
3. 변수 p를 1로 초기화하고, 문자열을 뒤에서부터 순회하며 v배열에 등장표시, w배열에 가중치를 저장한다.
4. 정수형 벡터 letters를 초기화하고, 실제 등장한 문자의 인덱스를 letters에 추가한다.
5. 변수 zero를 -1로 초기화 하고, 실제 등장한 문자 개수가 10개 이상인 경우 zero에 0이될 문자의 인덱스를 저장한다.
6. sort함수를 통해 문자의 인덱스를 letters를 가중치 w를 기준으로 비교하여 정렬한다.
7. 변수 d를 9로 초기화하고, letters를 순회하며 각 문자에 할당될 값을 val배열에 초기화한다.
8. 변수 ans를 0으로 초기화하고, 등장한 문자일 경우 ans에 w[i]와 val[i]의 곱을 더해준다.
9. ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 0이 될 수는 가중치를 기반으로 탐색하되 문자열의 가장 첫 문자로 등장하지 않은 문자끼리만 비교한다.
2. 가중치가 가장 높은 순서대로 9에서부터 내림차순으로 값을 할당한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

const int N = 50;
ll w[10];
bool f[10];
bool v[10];
int n;
int val[10];
string words[N];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> words[i];

    for (int i = 0; i < n; ++i) {
        const string& s = words[i];
        int len = s.size();
        f[s[0] - 'A'] = true;

        ll p = 1;
        for (int i = len - 1; i >= 0; --i) {
            int idx = s[i] - 'A';
            v[idx] = true;
            w[idx] += p;
            p *= 10;
        }
    }

    vector<int> letters;
    for (int i = 0; i < 10; ++i) {
        if (v[i]) letters.push_back(i);
    }

    int zero = -1;
    if (letters.size() >= 10) {
        ll mn = 1e18;
        for (int idx : letters) {
            if (!f[idx] && w[idx] < mn) {
                mn = w[idx];
                zero = idx;
            }
        }
    }

    sort(letters.begin(), letters.end(), cmp);

    int d = 9;
    for (int idx : letters) {
        if (idx == zero) continue;
        val[idx] = d--;
    }

    ll ans = 0;
    for (int i = 0; i < 10; ++i) {
        if (v[i]) ans += w[i] * val[i];
    }

    cout << ans;
}