[BOJ-1339] 단어수학

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

1339번: 단어 수학

---

[ 풀이 ]

백트래킹으로 시도하려다가, 백트래킹으로하면 시간초과가 나왔고

스터디 멤버와 블로그 탐색을 도움삼아서 다시 시도했다.

풀이 방법은 그리디를 이용하여 풀었다.

 

(1) 문자열 길이를 기준으로 정렬한다.

[ GCF, ACDEB ] =>[ ACDEB, GCF ]

 

(2) 알파벳이 위치한 자릿수를 더한다.

alpha[A~Z]=0으로 초기화 한다.

 

예를 들자면 GCF의 G는 100의 자리이므로

alpha[G]=alpha[G]+100 이다.

 

마찬가지로 C는 10의 자리이므로

alpha[C]=alpha[C]+10

 

두 단어에 있는 모든 알파벳들을 구하면

alpha[A]=10000

alpha[B]=1

alpha[C]=1010

alpha[D]=100

alpha[E]=10

alpha[F]=1

alpha[G]=100  이 나온다.

 

* 단어의 개수는 N=1~10이고 단어에 대응하는 숫자값은 0~9이다.

 

(3) alpha값을내림차순 정렬시킨다.

그리고 9부터 시작하여 차례대로 더한다.

 

백트래킹보다 그리디를 이용하면 더 효율적으로 풀 수있다.

---

[성공 코드]

# 단어 수학 재도전 -> greedy를 이용해서 풀이
import sys
input = sys.stdin.readline

N= int(input())
words=[ input().strip() for _ in range(N)]

#문자열 길이대로 정렬
words=sorted(words)

alpha=[0]*26
for word in words:
    for idx, w in enumerate(word):
        alpha[ord(w)-ord('A')]+=10**(len(word)-1-idx)

#alpha를 내림차순으로 정렬한다.
alpha=sorted(alpha, reverse=True)

ans=0
for i in range(9,0,-1):
    ans= ans+ (i * alpha[9-i])
print(ans)

---

[실패 코드]

1) 풀이

- 백트래킹을 이용하여 풀었다.

- 단어의 길이가 긴것을 우선으로 정렬했다.

- used_word는 사용한 단어에 포함된 알파벳 순서대로 나열했다.

맨앞에 있는 알파벳을 9로 했고, 차례대로 내려가면서 했다.

 

2) 채점결과 : 시간초과가 떴다ㅠㅠ.

import sys
from copy import deepcopy
sys.setrecursionlimit(10**9)
input=sys.stdin.readline

max_val=0 #가장큰 값
def backtracking(idx, word2Num, visited):
    global N, used_word, max_val
    
    if idx==len(used_word)-1: #마지막 원소인가?
        result=0
        for word in words:
            tmp=0
            for w in word:
                tmp+=word2Num[w]
                tmp*=10
            tmp= tmp//10
            result+=tmp
        max_val=max(max_val, result)

    else:
        for i in range(9,10-len(used_word)-1, -1):
            if visited[i]==0:
                tmp_visited=deepcopy(visited)
                tmp_visited[i]=1
                
                tmp_word2Num= deepcopy(word2Num)
                tmp_word2Num[used_word[idx+1]]=i
                backtracking(idx+1, tmp_word2Num, tmp_visited)
        
        
N=int(input().strip()) #단어개수
words=[ input().strip() for _ in range(N)] #단어

#단어길이를 기준으로 내림차순정렬
#=> 길이가 같을때는 알파벳순을 기준으로(기본값)
words=sorted(words, key=len , reverse=True)

#used_word :사용한 단어 (중복배제)
used_word=[]
for word in words:
    for w in word:
        if w not in used_word:
            used_word.append(w)

word2Num={}
visited=[0 for _ in range(10)] #0~10

word2Num[used_word[0]]=9
visited[9]=1
backtracking(0, word2Num, visited)
print(max_val)