Table of Contents
문제
주어진 문자열을 재조합해 팰린드롬 단어를 만들어라. 불가능할 경우 "I'm Sorry Hansoo" 출력.
예제
- 예제 1
1 2
입력: AABB 출력: ABBA
- 예제 2
1 2
입력: AAABB 출력: ABABA
- 예제 3
1 2
입력: ABACABA 출력: AABCBAA
- 예제 4
1 2
입력: ABCD 출력: I'm Sorry Hansoo
상황 파악과 계획
문제에서 요구하는 것: 주어진 글자들을 이용해 팰린드롬 만들기
계획: 알파벳 대문자만 주어지므로 카운팅 후 확인 및 팰린드롬 생성
- 홀수 개 등장한 글자가 2개 이상 있을 경우 팰린드롬 불가 ->
"I'm Sorry Hansoo" - 홀수 개 등장한 글자가 1개 이하일 경우, 해당 글자는 1개만 따로 빼두고 짝수 개 등장한 것으로 취급한다.
- 짝수 개 등장한 글자를 절반씩 먼저 앞에 놓고, 홀수 개 글자가 있을 경우 가운데 놓고, 이후 앞에 놓은 알파벳의 역순으로 다시 나머지 글자를 놓는다.
풀이
첫 번째 답안
타이머를 늦게 켜서 계획 시간 약간 빼고 정답 확인까지 22분 39초
- 사실 함수를 정의할 필요까지는 없었는데 코드를 어디 담아 정리하는 게 습관이다.
- 원래 계획은 사전순으로 팰린드롬 앞부분을 먼저 붙인 다음 사전 역순으로 팰린드롬 뒷부분을 붙이는 거였는데, 순서만 반대이고 똑같은 작업을 굳이 따로 해야 할까 싶어서 한번에 할 방법을 고민하다 팰린드롬의 가운데에서부터 양 옆으로 단어를 연장해가기로 했다.
ord()랑chr()정도는 이참에 외우면 좋겠다. 항상 까먹어서 다시 검색한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_palindrome(word: str) -> str:
alphabets = [0] * 26
int_a = ord('A')
ans = ""
middle_char = None
for char in word: # 글자 세기
alphabets[ord(char) - int_a] += 1
for i in range(26): # 팰린드롬 만들기 전 글자 구성 확인
if alphabets[i] % 2 != 0: # 홀수 개 있는 글자
if middle_char is None: # 처음 나왔으면 가운데 글자로 저장 후 짝수 개 취급
middle_char = chr(int_a + i)
ans = middle_char # 가운데 글자 먼저 놓기
alphabets[i] -= 1
else: # 또 나왔으면 팰린드롬 불가
return "I'm Sorry Hansoo"
alphabets[i] //= 2 # 결격사유가 없다면 짝수일 것
for i in range(25, -1, -1): # 양 옆에 짝수 글자 놓기
if alphabets[i] == 0:
continue
ans = (chr(int_a + i) * alphabets[i]) + ans + (chr(int_a + i) * alphabets[i])
return ans
print(make_palindrome(input()))
두 번째 답안
첫 번째 답안에서 비슷하게 생긴 반복문을 여러 개 쓰는 것 같아서 합쳐봤다. 글자 수가 짝수인지 홀수인지 확인함과 동시에 팰린드롬 단어를 만들기 때문에 가운데 글자를 넣는 부분이 조금 바뀌었다.
채점 시간은 44ms에서 40ms로 줄었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_palindrome(word: str) -> str:
alphabets = [0] * 26
int_a = ord('A')
ans = ""
middle_char = None
for char in word: # 글자 세기
alphabets[ord(char) - int_a] += 1
for i in range(25, -1, -1):
if alphabets[i] == 0:
continue
if alphabets[i] % 2 != 0: # 홀수 개 있는 글자
if middle_char is None: # 처음 나왔으면 가운데 글자로 저장 후 짝수 개 취급
middle_char = chr(int_a + i)
alphabets[i] -= 1
else: # 또 나왔으면 팰린드롬 불가
return "I'm Sorry Hansoo"
alphabets[i] //= 2 # 결격사유가 없다면 짝수일 것
ans = (chr(int_a + i) * alphabets[i]) + ans + (chr(int_a + i) * alphabets[i])
if middle_char is not None:
ans = ans[:len(ans) // 2] + middle_char + ans[len(ans) // 2:]
return ans
print(make_palindrome(input()))
세 번째 답안
최단시간 답안을 봤는데 딕셔너리를 사용하고 있어서 그 아이디어를 빌려 조금 더 바꿔봤다.
채점 시간은 40ms 그대로이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def make_palindrome(word: str) -> str:
alpha = {}
ans = ""
middle_char = None
for char in word: # 글자 세기
if char in alpha:
alpha[char] += 1
else:
alpha[char] = 1
for char in sorted(alpha.keys(), reverse=True):
if alpha[char] % 2 != 0: # 홀수 개 있는 글자
if middle_char is None: # 처음 나왔으면 가운데 글자로 저장 후 짝수 개 취급
middle_char = char
alpha[char] -= 1
else: # 또 나왔으면 팰린드롬 불가
return "I'm Sorry Hansoo"
alpha[char] //= 2
ans = (char * alpha[char]) + ans + (char * alpha[char])
if middle_char is not None:
ans = ans[:len(ans) // 2] + middle_char + ans[len(ans) // 2:]
return ans
print(make_palindrome(input()))