๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“š Algorithm/Baekjoon

[Baekjoon] ๋ฐฑ์ค€ 1339 '๋‹จ์–ด ์ˆ˜ํ•™' ๋ฌธ์ œํ’€์ด Python, ํŒŒ์ด์ฌ, ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋ฆฌ

 

๐Ÿ“ 1339 ๋ฌธ์ œ 

๋ฏผ์‹์ด๋Š” ์ˆ˜ํ•™ํ•™์›์—์„œ ๋‹จ์–ด ์ˆ˜ํ•™ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ์ˆ™์ œ๋ฅผ ๋ฐ›์•˜๋‹ค.

๋‹จ์–ด ์ˆ˜ํ•™ ๋ฌธ์ œ๋Š” N๊ฐœ์˜ ๋‹จ์–ด๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ฐ ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ด๋•Œ, ๊ฐ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋ฅผ 0๋ถ€ํ„ฐ 9๊นŒ์ง€์˜ ์ˆซ์ž ์ค‘ ํ•˜๋‚˜๋กœ ๋ฐ”๊ฟ”์„œ N๊ฐœ์˜ ์ˆ˜๋ฅผ ํ•ฉํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๊ฐ™์€ ์•ŒํŒŒ๋ฒณ์€ ๊ฐ™์€ ์ˆซ์ž๋กœ ๋ฐ”๊ฟ”์•ผ ํ•˜๋ฉฐ, ๋‘ ๊ฐœ ์ด์ƒ์˜ ์•ŒํŒŒ๋ฒณ์ด ๊ฐ™์€ ์ˆซ์ž๋กœ ๋ฐ”๋€Œ์–ด์ง€๋ฉด ์•ˆ ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, GCF + ACDEB๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค๊ณ  ํ•  ๋•Œ, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7๋กœ ๊ฒฐ์ •ํ•œ๋‹ค๋ฉด, ๋‘ ์ˆ˜์˜ ํ•ฉ์€ 99437์ด ๋˜์–ด์„œ ์ตœ๋Œ€๊ฐ€ ๋  ๊ฒƒ์ด๋‹ค.

N๊ฐœ์˜ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ทธ ์ˆ˜์˜ ํ•ฉ์„ ์ตœ๋Œ€๋กœ ๋งŒ๋“œ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

 

์ž…๋ ฅ 

์ฒซ์งธ ์ค„์— ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 10)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋‹จ์–ด๊ฐ€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๋‹ค. ๋ชจ๋“  ๋‹จ์–ด์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ์•ŒํŒŒ๋ฒณ์€ ์ตœ๋Œ€ 10๊ฐœ์ด๊ณ , ์ˆ˜์˜ ์ตœ๋Œ€ ๊ธธ์ด๋Š” 8์ด๋‹ค. ์„œ๋กœ ๋‹ค๋ฅธ ๋ฌธ์ž๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ์ˆซ์ž๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.

 

 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ฃผ์–ด์ง„ ๋‹จ์–ด์˜ ํ•ฉ์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

๐Ÿง ํ’€์ด

์œ„์˜ ๋ฌธ์ œ๋Š” ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์ด๋‹ค.

๋จผ์ € N๊ฐœ์˜ ๋‹จ์–ด๋ฅผ ์ž…๋ ฅ ๋ฐ›์•„์„œ word์— ์ €์žฅ์„ ํ•œ๋‹ค.

์•ŒํŒŒ๋ฒณ ๋ณ„๋กœ ์–ด๋–ค ์ˆซ์ž๋ฅผ ๊ฐ€์ง€๋Š” ์ง€ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด word_dict๋ฅผ ๋งŒ๋“ค๊ณ  ๊ฐ ์ˆซ์ž๋ฅผ ๋‹ด์„ num_list๋„ ๋งŒ๋“ ๋‹ค. 

๊ฐ ๋‹จ์–ด๋“ค์„ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ํ•˜๋‚˜์”ฉ ๋”ฐ์ ธ๋ณด๋ฉด์„œ word_dict์— ์žˆ๋‹ค๋ฉด, ์ž๋ฆฟ์ˆ˜๋ฅผ ์ฒดํฌํ•ด์„œ ๊ฐ’์„ ๋งค์นญ์‹œํ‚จ๋‹ค. 

๋งค์นญ ์™„๋ฃŒ  ํ›„ ๋”•์…”๋„ˆ๋ฆฌ์˜ value๊ฐ’๋“ค๋งŒ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค. ์ •๋ ฌํ•œ ์ˆœ์„œ๋Œ€๋กœ 9๋ถ€ํ„ฐ 1๊นŒ์ง€ ๊ณฑํ•˜๋ฉด ๋œ๋‹ค. 

 

N = int(input())
word = []	#๋‹จ์–ด ์ €์žฅ
word_dict = {}	#์•ŒํŒŒ๋ฒณ๊ณผ ์ˆซ์ž ์ €์žฅ
num_list = []	#์ˆซ์ž ์ €์žฅ

# N๊ฐœ์˜ ๋‹จ์–ด ์ž…๋ ฅ๋ฐ›๊ธฐ 
for i in range(N) :
    w = input()
    word.append(w)

# ๋‹จ์–ด๋“ค์„ ํ•˜๋‚˜์”ฉ ๋”ฐ์ ธ๋ณด๋ฉด์„œ ์ž๋ฆฟ์ˆ˜ ๊ณ„์‚ฐ
for i in range(N) :
    for j in range(len(word[i])) :
        if word[i][j] in word_dict :
            word_dict[word[i][j]] += 10  ** (len(word[i])-j-1)
        else :
            word_dict[word[i][j]] = 10 ** (len(word[i])-j-1)

# ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ
for i in word_dict.values() :
    num_list.append(i)
num_list.sort(reverse=True)

# 9๋ถ€ํ„ฐ ๊ณฑํ•ด์ฃผ๊ธฐ 
sum = 0
pows = 9
for i in num_list :
    sum += pows * i
    pows -= 1
print(sum)
 

 

 

728x90