[Java] 백준 풀기 1213 - 팰린드롬 만들기

자바 백준 1213번

실버 3

https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

 

 

 

 

문제 보기

분류: 구현, 그리디 알고리즘, 문자열

 

 

 

 

 

문제 풀기

주어진 이름에서 각 알파벳의 등장 횟수를 세고, 팰린드롬을 구성하는 절반을 만든 후에 이를 조합하여 전체 팰린드롬을 만든다. 만약 주어진 조건으로 팰린드롬을 만들 수 없다면 "I'm Sorry Hansoo"를 출력한다.

 

입력된 이름을 이용하여 각 알파벳의 등장 횟수를 세어 배열에 저장한다.

홀수 번 등장한 알파벳이 두 개 이상일 경우 return "I'm Sorry Hansoo".

홀수 번 등장한 알파벳이 한 개는 저장해 둔다.

등장한 알파벳은 사전 순서대로 절반을 생성한다.

홀수 번 등장한 알파벳이 있으면 중앙에 추가한다.

절반을 생성한 팰린드롬을 reverse()를 이용하여 뒤집고 추가한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String name = sc.nextLine();  // 사용자로부터 영어 이름을 입력받음
        
        String palindrome = createPalindrome(name);  // 함수로 입력된 이름으로 팰린드롬 생성
        
        System.out.println(palindrome);  // 생성된 팰린드롬 출력
    }
    
    public static String createPalindrome(String name) {
        int[] alphabetCount = new int[26];  // 알파벳 등장 횟수를 저장할 배열
        
        // 입력된 이름에서 각 알파벳의 등장 횟수를 세어 배열에 저장
        for (char c : name.toCharArray()) {
            alphabetCount[c - 'A']++;
        }
        
        StringBuilder halfPalindrome = new StringBuilder();  // 팰린드롬의 절반을 저장할 문자열
        char oddCharacter = 0;  // 홀수 번 등장한 알파벳을 저장할 변수
        
        // 각 알파벳의 등장 횟수를 확인하면서 팰린드롬의 절반을 구성
        for (int i = 0; i < 26; i++) {
            // 홀수 번 등장한 알파벳이 두 개 이상일 경우 팰린드롬 생성 불가능
            if (alphabetCount[i] % 2 == 1) {
                if (oddCharacter != 0) {
                    return "I'm Sorry Hansoo";
                }
                
                // 홀수 번 등장한 알파벳 저장
                oddCharacter = (char) ('A' + i);
            }
            
            // 알파벳 등장 횟수의 절반을 이용하여 팰린드롬의 절반을 생성
            for (int j = 0; j < alphabetCount[i] / 2; j++) {
                halfPalindrome.append((char) ('A' + i));
            }
        }
        
        StringBuilder palindrome = new StringBuilder(halfPalindrome.toString());
        
        // 홀수 번 등장한 알파벳이 있다면 중앙에 추가하여 전체 팰린드롬 생성
        if (oddCharacter != 0) {
            palindrome.append(oddCharacter);
        }
        
        // 팰린드롬의 절반을 뒤집어서 전체 팰린드롬 생성
        palindrome.append(halfPalindrome.reverse());
        
        // 생성된 팰린드롬 반환
        return palindrome.toString();
    }
    
}



/*
AABBCCCDD

ABCDCDCBA
*/