Gidhub BE Developer

[BOJ] 1339. 단어 숫자

2018-09-24
goodGid

Problem

Problem URL : 단어 숫자


[1] Answer Code (18. 09. 24)

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

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    set<char> se;
    vector<string> in;
    
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        in.push_back(s);
        for(int j=0; j<s.size(); j++)
            se.insert(in[i][j]);
    }
    
    set<char>::iterator iter;
    vector<int> alpha;
    for(iter = se.begin(); iter != se.end(); iter++){
        alpha.push_back(*iter - 'A' );
    }

    int arr[27];
    int ans = -1;
    sort(alpha.begin(), alpha.end());
    
    do{
        int sum = 0;
        // [1]
        for(int i=0, k=9; i<alpha.size(); i++, k--){
            arr[ alpha[i] ] = k;
        }
    
        for(int idx=0; idx<n; idx++){
            /*
             ABC라면
             C에 해당하는 값 * 1
             B에 해당하는 값 * 10
             A에 해당하는 값 * 100 을 해주는 코드이다.
             */
             // [2]
            for(int i=(int)in[idx].size()-1, mul = 1; i>=0; i--, mul *= 10){
                sum += arr[in[idx][i] - 'A'] * mul;
            }
        }
        ans = max(ans,sum);
    }while(next_permutation(alpha.begin(),alpha.end()));
    
    cout << ans << endl;
    return 0;
}

Review

  • set을 사용한 풀이다.

  • 단순한 로직이였지만 next_permutation을 대상을 어떻게 잡아줘야하는지를 처리하는 부분이 까다로웠다.

  • A의 ASCII값은 고정이다. 그렇기 때문에 A의 해당하는 arr배열 인덱스도 또한 고정이 된다.

  • 여기서 중요한 점은 그 인덱스에 들어있는 값을 1회전마다 바꿔주는 것이다.

  • 그리고 주어진 input을 1글자씩 쪼개써 arr배열을 참조할 때 1회전 마다 바뀐 값으로 계산을 하여 최적의 답을 구하는 것이다.

사용된 알파벳이 A B C 이고
그 ASCII값이 1 5 9 이라고 가정해보자.

부여할 가중치 값  : 9 8 7 
사용된 Alphabet : A B C
arr의 index    : 1 5 9

[1] 코드에 의해 
arr[1] = 9;
arr[5] = 8;
arr[9] = 7; 처럼 초기화가 될 것이다.

그 후 next_permutation을 돌려서
"ABC"를 "ACB"로 바꾼다.

그렇게 되면 [1] 코드에 의해 
arr[1] = 9;
arr[5] = 7;
arr[9] = 8; 로 초기화가 된다.

다시말해 위치는 고정이고
그 안에 있는 값만 바뀌게 하는 것이다.

그러면 [2] 코드에 의해 
값을 구할 때는 
  Before   After
A : 9   ->   9
B : 8   ->   7
C : 7   ->   8 로 맵핑이 된다.

이 작업이 반복되면 DFS처럼 모든 경우의 수를 다 볼 수 있다.

사실 처음엔 next_permutation의 대상을 arr로 했다.
그랬더니 너무나 많은 시간이 걸렸다. 
(사실은 잘못된 로직이라 판단이 들었기 때문에 함수가 종료되기 전에 중지를 했다.)
  • 1개의 Key 값의 사용 유무를 판단할 때는 set을 사용하는게 좋다.

  • Key / Value 구조라면 map을 사용하는 것도 고려해보자.

  • 알고리즘 힌트는 AC 1339 단어수학 블로그에서 받았다.


Comments

Content