단어 수학

문제: 단어 수학 (백준 1339번)

구조 분석

해당 문제는 마방진 문제이다. 알파벳이 주어지고 이에 각각 숫자를 대입하여 결과를 얻는 문제인데 처음에는 이 문제를 어떻게 풀지 고민은 많이 했다. 최대 10개의 알파벳이 주어지므로 각각 알파벳에 0~9까지 숫자를 모두 대입해보는 brute force방식으로 풀 수 있다고 생각했지만 그거 보다 더 효율적인 방법이 greedy algorthm을 이용하는 방식이다.

풀이 방법

각각 문자열을 입력받아서 해당 문자열의 각 알파벳에 1, 10, 100 등의 단위를 부여한 뒤 전체 알파벳을 단위가 큰 순서로 정렬하여 큰 알파벳부터 9, 8, 7 …을 차례로 대입하는 방법이다.
예를 들어서 “ABC”라는 문자열을 입력받으면 A = 100, B = 10, C = 1을 부여한다. 이를 이후에 크기 순으로 정렬하여 차례로 A = 9, B = 8, C = 7을 대입하여 계산을 해주는 것이다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int alphabet[26] = {0,};

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

int main() {
    int N;
    cin >> N;
    for (int i=0; i<N; i++) {
        string input;
        cin >> input;
        int len = input.length();
        int pow = 1;
        for (int j=len-1; j>=0; j--) {
            int idx = input[j] - 'A';
            alphabet[idx] += pow;
            pow *= 10;
        }
    }
    sort(alphabet,alphabet+26,compare);
    int ans = 0;
    int num = 9;
    for (int i=0; i<26; i++) {
        if (alphabet[i] == 0) break;
        ans += (alphabet[i] * num);
        num--;
    }
    cout << ans << "\n";
    return 0;
}

정리

문자열을 입력받아서 알파벳 별로 단위를 입력받는다는 생각을 하는 것이 포인트였다. 예를 들어서 “ABC”, “BA” 문자열이 주어질 때, A = 101, B = 20, C = 1을 부여받게 되는 상황을 생각해야 한다. 그리고 구현에 있어서 alphabet[26] 배열을 만들어 input - 'A'로 해당 배열의 index를 찾아 증가시켜주는 생각이 단순하면서도 떠올리기 힘들었다. 이러한 것에 익숙해져야 string 문제도 잘 풀 수 있게 되는 것 같다.