[Algorithm] 백준 - ReMorse

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

 

 

모스부호는 점(dot)과 대시(dash) 기호의 배열을 알파벳 문자에 할당한 것이다. 모스 부호의 배열을 다시 지정하여 주어진 메세지가장 짧은 길이를 반환하도록 해라. 

 

• dot : 1 
• dash : 3 
• 기호 사이 간격: 1 
• 문자 사이 간격: 3  

단, 공백, 구두점, 알파벳 대소문자는 무시된다.  

---

 

💡해결한 아이디어 

 

가장 짧은 길이를 반환하기 위해서는 "빈도수가 높을 수록 작은 길이의 모스부호 배열을 할당" 해야 한다는 것이다.  

 

1. 주어진 메세지가 알파벳인지 확인. 만일 알파벳이라면 대문자 변환한 다음 공백 제거  

s = input() 
filter_s = "".join([char.upper() for char in s if s.isalpha()])

 

2. 단어의 빈도수를 계산하기 위해 Counter 함수로 계산, 단어 당 빈도수를 내림차순으로 정렬 

from colleciont import Counter 

cnt_word = list(Counter(filter_s).values())
cnt_word = sorted(cnt_word, reverse = True)

 

3. 문자길이별, dot 과 dash를 활용하여 만들 수 있는 모스부호 조합 개수 구하기   

• 우선은 dot이 가장 짧은 길이를 가지므로 dot을 기준으로 생각
• dot 2개의 길이는 dash 1개의 길이, 즉 3으로 동일하다.  (•• = – )   

dot의 개수를 n, dash의 개수를 m이라고 할 때,  문장의 길이는 다음과 같습니다. 

 

문장의 길이 = 1 × n + 3 × m + (n+m-1) = 2n + 4m -1  

 

길이에 따라 나올 수 있는 n과 m의 조합 !! 

문장길이	n과m의 조합(n,m)					해당 길이가 나올 수 있는 모스부호 배열 수
1	(1,0)					1
3	(2,0)	(0,1)				2
5	(3,0)	(1,1)				3
7	(4,0)	(2,1)	(0,2)			5
9	(5,0)	(3,1)	(1,2)			8
11	(6,0)	(4,1)	(2,2)	(0,3)		13
13	(7,0)	(5,1)	(3,2)	(1,3)		21
15	(8,0)	(6,1)	(4,2)	(2,3)	(0,4)	34
17	(9,0)	(7,1)	(5,2)	(3,3)	(1,4)	55

  

 

예를 들어 (1,1) 일경우 • – , – • 로 2가지의 배열이 나올 수 있다. 

 

 

문장의 길이 1 , 3 , 5 , 7 , 9...  로 2씩 증가하며,  해당 길이가 나올 수 있는 모스부호 배열 수는 1 , 2 ,3 ,5, 8, ... 피보나치 수열 순이다. 

 

• 문장의 길이가 1 → 모스부호 배열 수 1개 
• 문장의 길이가 3 → 모스부호 배열 수 2개
• 문장의 길이가 5 → 모스부호 배열 수 3개

 

즉, 리스트로 나타낸다면 [ 1 , 3 , 3 , 5 , 5 , 5 ,7 ,7 ,7 ,7 ,7 ,9 ,9 ,9 ,9 ,9 ,9 ,9 ,9 ... ] 로 나타낼 수 있다. 

 

cnt = 1 
f1 , f2 = 1 , 2 #현재 피보나치 수 만큼 숫자 추가 
result = [] #문장길이를 담을 리스트 

n = len(answer) 

while len(result) < n : #주어진 문장의 길이만큼 반복합니다. 
	result.extend([cnt] * fbi) 
    f1 , f2 = f2 , f1 + f2  #다음 피보나치 수 업데이트 
    cnt += 2  
    
 result = result[:n]

 

 

4.  가장 높은 빈도 문자열에 낮은 길이의 모스 부호 배열을 할당 ⭐⭐

 

오름차순으로 정렬한 모스부호배열의 길이와 내림차순으로 정렬한 문자별 빈도수를 곱해준다.

이 때 , 단어 사이의 간격은 3이므로 (문장 길이 - 1) × 3을 더해준다. 

 

total_length = sum([ a*b for a, b in zip( cnt_word ,  result)]) + (len(filter_s) -1) *3 
print(total_length)

 

 

⭕ 최종코드 

 

from collections import Counter

s = input()
# 알파벳인지 확인 및 공백제거, 대문자 변환
filter_s ="".join([char.upper() for char in s if char.isalpha()])  

# 문자별 빈도 수 내림차순
cnt_word = sorted(list(Counter(filter_s).values()), reverse=True)

current_num = 1
f1, f2 = 1, 2
result = []

n = len(cnt_word)

while len(result) < n:
    result.extend([current_num] * f1)
    current_num += 2 
    f1, f2 = f2, f1 + f2  # 피보나치 수 업데이트

result = result[:n]
total_length = sum([a * b for a, b in zip(cnt_word, result)]) + (len(filter_s) - 1) * 3
print(total_length)

---