[백준] No.1339 - 단어 수학 (C++)

문제

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

1339번: 단어 수학

 

풀이

 

solved.ac 난이도: Gold 4

 

아이디어는 단순했지만 구현하기가 까다로워서 코드가 엉망 친창이 되어버렸다..

 

문제를 파악했다면 높은 자릿수에 자주 나오는 알파벳일 수록 큰 수를 대입해 주면 된다는 것을 알 수 있을 것이다.

예를 들어 아래와 같은 입력이 주어졌다고 생각해보자.

 

ACA

BCC

 

여기서 100의 자리 수는 A와 B 두 가지가 존재한다.

그렇다면 A와 B 중에서 어떤 수가 9가 되어야 할지는 각 알파벳이 몇번째 자리 수 에서 몇번 등장하는지 계산을 해주어야한다.

위의 예제에서는 

A는 100의 자리와 1의 자리에 각각 한 번씩 등장하는 반면, B은 100에 자리에만 한번 등장한다. 따라서 A에는 9, B에는 8을 대입해 주어야 단어의 합이 최댓값이 될 수 있다.

 

이러한 우선순위를 숫자로 표현하기 위해 아래처럼 각 알파벳이 등장한 자리 수의 위치만큼 가중치를 주자.

A: 101

B: 100

C: 021 (10의 자리 2번, 1의 자리 1번)

이를 구현하기 위해 아래와 같이 코드를 작성하였다.

 

단어를 역순으로 끝에서부터 어떤 알파벳이 나오는지 확인하다. 등장한 알파벳(alpabet)은 appearance_count[alpabet][order]에 몇 번째(order)에서 등장하였는지 저장해 주자.

for(int i=0; i<word_num; ++i){
    order =0;
    for(int idx= word_arr[i].length()-1 ;  idx>=0 ; --idx){
      alpabet = word_arr[i][idx]- 'A';
      ++appearance_count[alpabet][order++];
    }
}

 

다음으로는 저장해둔 appearance_count를 이용하여 어떤 알파벳이 높은 수를 부여받아야 하는지 저장한다.

for(int i=0; i<26 ; ++i){
    priority[i].first = 0; // first에는 가중치
    priority[i].second = i; // second에는 몇번쨰 알파벳인지를 저장
    for(int order=7; order>=0 ; --order){
      priority[i].first += appearance_count[i][order];
      priority[i].first *= 10;
    }
}

이때의 priority는 pair<int,int>로 선언하여 각 알파벳이 어떤 우선순위를 가지는지 저장할 수 있게 한다.

priority[i].first에는 i번째 알파벳이 해당 자리 수(order)에 몇 번 등장했는지 더해주고

다음 order로 넘어가기 전에 x10을 해주어 가중치를 주자.

 

이때 처음에는 최대 10개의 단어이기 때문에 같은 자리 수에서 10번 모두 등장하는 알파벳이 있다면 더해주는 값이 일의 자리가 아닌 10을 더해줘야 하기 때문에 x100을 해주어야 된다고 생각했다.

 

예를 들어 아래처럼 입력이 주어진다면

AB

B

B

B

B

B

B

B

B

B

 

가중치 계산은 아래처럼 똑같이 나타난다.

A: 10 (10의 자리 한번)

B: 10 (1의 자리 10번)

 

이런 경우를 분류하기 위해 x100을 해준다면 아래처럼 가중치가 설정될 것이다.

A: 100 (10의 자리 한번)

B: 010 (1의 자리 10번)

 

하지만 아래와 같은 예제에서는 X100을 하는 계산은 틀리다는 것을 알 수 있다.

 

ABB

BB

BB

BB

BB

BB

BB

BB

BB

BA

 

A: 1/00/01 (100의 자리 한번, 1의 자리 한번)

B: 0/10/09 (10의 자리 10번, 1의 자리 9번)

 

x100의 가중치라면 A가 9를, B는 8을 할당받아 더한 값이 아래와 같이 나타난다.

 

988+88 × 8+89=1781

 

반면 x10의 가중치라면 

 

A: 101 (1/0/1 100의 자리 한번, 1의 자리 한번)

B: 109 (/10/9 10의 자리 10번, 1의 자리 9번)

로 B가 9를 할당받는다.

 

이런 경우

899+99 × 8+98 = 1789 이기 때문에 더 큰 값을 같는다.

즉, x10을 통해 10번 등장한 경우는 자리가 올림 되는 게 타당하다.

 

 

이제는 priority 정렬을 해준후 priority.first 가 큰 수부터 높은 번호를 할당하여 값을 계산하면 된다.

 

 

코드