백준 1213번 팰린드롬 만들기 - Python
문제
임한수와 임문빈은 서로 사랑하는 사이이다.
임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.
임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데,
임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.
임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.
입력
첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.
출력
첫째 줄에 문제의 정답을 출력한다.
만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다.
정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.
문제해설
팰린드롬이란, 앞에서 읽은 것과 뒤에서 부터 읽은 것이 같은 문자를 의미한다.
본 문제는 주어진 문자열 입력을 가지고 팰린드롬을 만드는 문제이다.
불가능한 경우엔 정해진 출력문이 존재한다.
따라서, 만드는 것이 가능한지, 불가능한지 판단할 기준이 필요하다.
또한, 여러개의 팰린드롬이 나올 수 있기 때문에, 사전순으로 반드시 정렬해줘야 한다.
문제를 통해 먼저 파악한 것은, 주어진 입력의 String에서 순서는 아무런 의미가 없다는 것이다.
따라서, Hash를 통해 각 단어의 Count를 계산하고 저장했다.
이 때, Key값을 사전순으로 정렬해서, 사전 순으로 먼저 오는 단어를 먼저 사용할 수 있도록 했다.
반복문을 순회하면서, 투 포인터를 사용했다.
2개 이상의 단어가 남은 경우, 해당 단어를 맨 앞과 맨 뒤에 하나씩 넣는다.
그리고, 두 포인터의 위치가 겹치는 순간은 중간 점이기 때문에,
그 때는 개수가 1개인 단어를 넣어주었다. (홀수인)
그렇게 문자열을 수정해주고, 정답 문자열에서 '-' 문자가 하나라도 존재하면,
팰린드롬을 만들지 못하는 경우가 되기 때문에, 정해진 문구를 출력하였으며,
아닌 경우에는 완성된 문구를 출력했다.
정답 코드는 아래와 같다.
정답코드
pal = input()
tmp_dict = {p:0 for p in pal}
tmp_dict = sorted(tmp_dict.items(), key=lambda x: x[0])
string_dict = {}
for key, val in tmp_dict:
string_dict[key] = val
answer = ['-' for _ in range(len(pal))]
for p in pal:
string_dict[p] += 1
for front in range(len(pal) // 2 + 2):
compare = len(pal) - front - 1 # 뒷 비교문자
if front == compare:
for item, val in string_dict.items():
if val % 2 != 0 and val > 0:
answer[front] = item
string_dict[item] -= 2
break
else:
for item, val in string_dict.items():
if val >= 2:
answer[front] = item
answer[compare] = item
string_dict[item] -= 2
break
if '-' in answer:
print("I'm Sorry Hansoo")
else:
print(''.join(answer))