1️⃣ BOJ 1213 - 팰린드롬 만들기
문제 링크
문제 설명
임한수와 임문빈은 서로 사랑하는 사이이다.
임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.
임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.
임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.
입력
첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.
예시
정답
S = input()
L = [0 for _ in range(26)]
for i in S:
L[ord(i)-65] += 1
print_list = []; mid = ''
odd = 0
for i in range(len(L)):
if L[i] == 0:
continue
if L[i] % 2 == 1:
odd += 1
mid = chr(i+65)
print_list.append(chr(i+65)*(L[i]//2))
if odd > 1:
print("I\'m Sorry Hansoo")
else:
result = ''.join(print_list) + mid + ''.join(reversed(print_list))
print(result)펠린드롬은 거꾸로 읽어도 똑같은 단어이다.
모든 글자수를 카운트해서 홀수개인 문자가 1개 이하면 펠린드롬을 만들 수 있다.
- 문자열의 모든 글자수를 카운트한다.
- 출력용 리스트에 짝수개인 글자를 순서대로 삽입한다.
- 가운데에 넣을 문자는 따로 관리한다.
a. 이때 가운데에 넣을 문자가 2개 이상인 것은 카운트해서 예외처리한다. - 출력용 리스트와 가운데 문자를 이용해 펠린드롬을 출력한다.
디렉토리를 사용하거나 하는 방식으로 리팩토링이 가능할 것 같다.
2️⃣ BOJ 1141 - 접두사
문제 링크
문제 설명
접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.
단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.
출력
첫째 줄에 문제의 정답을 출력한다.
예시
정답
N = int(input())
L = []
for _ in range(N):
S = input()
is_out = False
for i in L:
if len(S) >= len(i):
if S[:len(i)] == i:
L.pop(L.index(i))
else:
if i[:len(S)] == S:
is_out = True
break
if not is_out:
L.append(S)
print(len(L))단어의 개수가 적어서 쉽게 접근할 수 있었다.
접근 방식은 만약 “hi”와 “high” 가 있다고 한다면 단어리스트에서는 더 짧은 “hi”를 제외시키는 것이 단어를 더 적게 제외시키므로 단어를 입력받을 때마다 부분집합이 발견되면 더 짧은 단어를 리스트에서 제외시키는 방식을 택했다.
- 단어를 입력받는다.
- 리스트를 순회한다.
- 부분집합이 있을 때
- 입력받은 단어가 짧은 단어라면 리스트에 추가하지 않는다.
- 리스트의 단어가 짧은 단어라면 리스트에서 제외시킨다.
- 리스트에 추가시킨다. (a-i 경우 제외)
- 부분집합이 있을 때
- 리스트의 길이를 출력한다.
중간에 코드를 짜면서 이게 그리디로 적용이 되는 문제인가 싶었지만, 곰곰히 생각해보니 더 짧은 단어를 제외시키는 것이 최적 부분 구조임을 알 수 있었다.
