문제
풀이 방법
백준을 풀다보면 팰린드롬 문제를 많이 만난다. 팰린드롬이란 뒤집어도 같은 문자열을 말한다. 따라서 홀수개인 알파벳이 0개이거나 1개만 있어야한다. 이것만 알고 있다면 이번 문제는 어렵지 않아 쉽게 풀 수 있다.
전반적인 흐름은 입력받은 알파벳들을 출현 횟수 / 2 만큼 A부터 더하고 Z까지 완료하면 만든 문자열을 뒤집어서 변수에 저장한 뒤
홀수인 알파벳이 1개이면 현재 문자열 + 홀수인 알파벳 + 뒤집은 문자열을 출력하고
홀수인 알파벳이 없으면 현재 문자열 + 뒤집은 문자열을 출력한다.
1. 알파벳을 배열로 입력 받기
대문자 알파벳만 주어지는데 대문자 A는 아스키코드로 65이고 Z는 90 이다. 따라서 26개짜리 int 배열을 선언하고 각 인덱스를 A부터 Z라고 생각하고 각 값은 해당 알파벳의 출현 숫자로 생각하면 된다.
따라서 배열을 입력 받을 때 문자열의 각 요소를 char로 바꾼 뒤 65를 뺀 인덱스 값을 +1 하도록 했다.
2. 출현 횟수가 홀수인 알파벳의 개수 세기 및 홀수일 경우 해당 알파벳 기록해두기
홀수인 알파벳은 1개까지는 허용된다. 따라서 홀수인 알파벳이 생겼을 경우 기록해두고 int 변수를 잡아서 홀수인 알파벳의 개수를 세야한다. 만약 홀수인 알파벳이 1개를 초과하면 I'm Sorry Hansoo를 출력하고 종료한다.
홀수인 알파벳이 1개만 있다면 두가지 경우로 나뉜다.
1. 해당 알파벳의 출현 횟수가 1인 경우
만약 출현횟수가 1인 경우 해당 알파벳이 어떤 알파벳인지 변수에 저장만 해둔다.
2. 해당 알파벳의 출현 횟수가 1을 초과하는 홀수일 경우
만약 출현횟수가 3 이상인 홀수라면 1개를 빼고는 현재 만들고 있는 문자열에 더해주어야한다. 예를 들어 5번 출현했으면 1개를 뺸 4개에서 2를 나는 2개를 더해주어야한다. 4개를 안더하고 2개만 더하는 이유는 어차피 뒤집은 문자열을 나중에 더할 것이기 때문에 지금 더한 횟수 * 2만큼 최종 문자열에 출현하기 때문이다.
3. 출현 횟수가 짝수인 알파벳의 경우 출현횟수 / 2 만큼 더하기
출현 횟수가 짝수이면 출현횟수 / 2 만큼 현재 만들고 있는 문자열에 더해주면 된다.
4. Z까지 완료한 뒤 현재 만든 문자열을 뒤집어서 변수에 저장해두기
A ~ Z까지 완료한 뒤 팰린드롬을 만들기 위해 현재까지 만든 문자열을 뒤집고 변수에 저장해두어야한다. 나중에 더해주어야하기 때문이다.
5. 출현 횟수가 홀수인 알파벳이 있으면 현재 문자열에 더해주기
만약 출현 횟수가 홀수인 알파벳이 있으면 2번에서 1개를 빼고는 더해주었으므로 홀수인 알파벳 1개를 현재 문자열에 더해준다.
6. 현재까지 만든 문자열에 아까 저장한 뒤집은 문자열을 더한 뒤 출력하기
현재까지 만든 문자열에 아까 저장한 뒤집은 문자열을 더한 뒤 출력하면 정답이 나온다.
정답 코드
import java.io.*;
public class p1213 {
public static void main(String[] args) throws IOException {
int [] alphabets = new int[26]; // idx 0은 65인 A부터 시작
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 입력 받기
String line = br.readLine();
String[] inputs = line.split("");
for (String s : inputs){
char c = s.charAt(0);
int idx = c-65;
alphabets[idx] ++;
}
int noPair = 0; // 홀수인 것의 개수
char noPairAlphabet = 0;
for(int i=0; i<26; i++){
int alphabetCnt = alphabets[i];
char alpha = (char) (i+65);
if(alphabetCnt % 2 != 0){
if(alphabetCnt / 2 > 0){ //홀수이지만 1개는 아닌 경우
for(int j=0; j<alphabetCnt / 2; j++){
sb.append(alpha);
}
}
noPairAlphabet = (char) (i+65);
noPair++;
if(noPair >1){ // 홀수개인 알파벳이 1개를 초과하는 경우
bw.write("I'm Sorry Hansoo");
bw.flush();
bw.close();
return;
}
}else {
// 짝수개인 경우
for(int j=0; j<alphabetCnt / 2; j++){
sb.append(alpha);
}
}
}
//현재까지의 sb 뒤집기
String reverse = sb.reverse().toString();
// 다시 원래대로 뒤집기
sb.reverse().toString();
// 만약 홀수개인 것이 1개 남았으면
if(noPair == 1){
sb.append(new String(String.valueOf(noPairAlphabet)));
}
sb.append(reverse);
bw.write(sb.toString());
bw.flush();
bw.close();
}
}