안녕하세요! 이번에는 백준 1213번 팰린드롬 만들기 문제를 풀어보겠습니당
문제
처음 문제를 보면 "팰린드롬"이라는 말이 눈에 띕니다.
팰림드롬이란? 앞으로 읽으나 뒤로 읽으나 같은 단어나 문장을 의미합니다!
예를 들어서 '토마토, 기러기, 080' 뭐 이러한 것들이 있겠지요
더 이어서 설명을 하자면 사용자가 입력한 문자열을 팰린드롬으로 만들 수 있다면
- 만든 것을 출력하면 되고
불가능하면
- "I'm sorry Hansoo"를 출력하면 된다
알고리즘
이 문제를 처음 봤을 때 생각난 것이 문자의 개수가 홀수일 때, 짝수일 때의 경우의 수를 나누어야겠다는 것
- 홀수개가 있다면 정가운데 한 문자를 제외하고 나머지는 대칭을 이루어야 함
- 짝수개가 있다면 (문자의 개수/2)와 그 다음 문자 사이를 대칭축으로 생각해야함
그래서 대칭축을 그리고 for문을 사용해서 한 글자씩 비교하려고 했다
근데 이렇게 하면 비교는 쉽지만 팰린드롬으로 만들기에 너무 복잡해진다
다른 방법을 생각해보니 문자가 짝수개만큼 있으면 되지 않을까 싶더라고요
이 접근 방식으로 시작!!
코드
역시나 자바를 이용했습니다
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon1213_2 {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 사용자 입력 str에 저장
String str = br.readLine();
// 모든 알파벳이 나타나는 횟수를 저장하기 위한 배열
int[] arr = new int[26];
// 사용자 입력 문자를 읽어서 아스키코드로 변환 후 횟수 arr에 저장
for (int i=0 ; i<str.length() ; i++) {
int index = str.charAt(i) - 'A';
arr[index]++;
}
// 짝수개가 아니라 하나만 등장하는 문자를 찾기 위한 명령
// num은 1개만 존재하는 문자의 위치를 저장하기 위한 변수
// odd는 횟수를 카운트하는 변수
int num = 0;
int odd = 0;
for (int i=0 ; i<arr.length ; i++) {
if (arr[i] % 2 != 0) {
odd++;
num = i;
}
// 둘 이상의 문자가 홀수 번 등장하면 팰린드롬이 성립하지 않음 -> 프로그램 종료
if (odd > 1) {
System.out.println("I'm sorry Hansoo");
return;
}
}
//팰린드롬을 만드는 명령
for (int i=0 ; i<arr.length ; i++) {
// arr[i] 안에 전체 개수만큼 문자가 들어가있으니 그거의 반만 sb에 대입
for (int j=0 ; j<arr[i]/2 ; j++) {
sb.append((char)(i+'A'));
}
}
// sb를 문자열로 변환
String result = sb.toString();
// 만약 문자열이 홀수자리였다면 가운데 문자도 추가
if (odd == 1)
result += (char)(num+'A');
//추가 후 sb에 있는 것들을 뒤집어서 다시 추가 -> 팰린드롬 완성
result += sb.reverse().toString();
System.out.println(result);
}
}마무리
처음에 생각했던 문자의 위치가 쓸모가 없었다..
사실 문자를 다시 재배열하는 것이기 때문에 홀수개 등장하는 문자만 조심해서 잘 생각하면 쉽게 풀리는 문제이다
파이썬이 아니라서 문자열을 붙이는 것이 조금 까다롭다고 느껴졌는데 StringBuilder를 이용하니 역순으로 char 하나씩 붙이는 것이 쉬워졌다
내장 함수들이나 클래스들을 아직 잘 모르는 느낌이라 조금 더 공부를 해야겠다
