뇌가 돌아오는중 (그리디, 브루트포스)

제주 여행을 다녀왔다. (2/7~2/9)

운전을 너무 많이하고 술과 커피에 쩔어있다보니

여행이 끝난 후 3일을 내리 잠만 잤다 (하루 10시간)

 

너무 피곤해서 계속 브론즈만 풀다가

오늘 드디어 골드를 풀었다!

 

(뇌가 풀렸다는 뜻. 아마도)

 

그리디와 브루트포스에 대해 알아보자

 

Greedy (그리디) : 탐욕스러운, 욕심많은

매 순간 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

Brute Forde (브루트 포스) : 무식한, 힘

가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

예외 없이 100% 확률로 정답만을 출력한다.

 

 

#1339 단어수학 https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

이 문제를 풀면서 나는 그리디와 브루트포스를 혼동했다.

 

일단 모든 경우의 수를 탐색하고자 코드를 짰다.

 

from itertools import permutations

N = int(input())
alpha = set()
s = []

for _ in range(N):
    tmp = []
    for x in input():
        alpha.add(x)
        tmp.append(x)
    s.append(tmp)
# print(alpha, s)

alpha = list(alpha)

answer = 0
for pers in permutations(alpha):
    tmp_list = []
    for i in range(len(s)):
        tmp = ""
        for j in range(len(s[i])):
            tmp += str(10 - (pers.index(s[i][j])+1))
        tmp_list.append(tmp)
    # print(tmp_list)
    a = 0
    for t in tmp_list:
        a += int(t)
    answer = max(a, answer)

print(answer)

로컬에서 예제만 굴리는데도 엄청오래걸렸다. 역시나 시간초과

 

이 문제는 부르트 포스보다는 그리디 알고리즘이 더욱 적합하다.

 

저렇게 모든 알파벳에 모든 숫자를 수열로 조합하는 것 보다는

자릿수가 큰 알파벳에 9부터 대입하는게 효율적이다.

 

구글링으로 아이디어를 얻을 수 있었다.

 

N = int(input())

cals = {}

for _ in range(N):
    s = input()
    for i in range(len(s)):
        try:
            cals[s[i]] += 10**(len(s)-i-1)
        except:
            cals[s[i]] = 10**(len(s)-i-1)

values = sorted(cals.values(), reverse=True)
answer = 0
for idx, v in enumerate(values):
    answer += v * (9-idx)

print(answer)

일단 입력을 받을 때 자릿수를 저장한다.

 

그 다음에 큰 자릿수를 가지고 있는 알파벳부터 9-8-7... 순서대로 대입한다.

 

최적해를 구했다.

 

그리디 끝!