[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1213번, 팰린드롬 만들기

문제 링크

1213번: 팰린드롬 만들기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 영어이름을 팰린드롬으로 만들어서 결과로 출력합니다.

2. 팰린드롬으로 만들지 못하면 "I'm Sorry Hansoo"를 결과로 출력합니다.

3. 팰린드롬은 순서대로 읽거나 반대로 읽어도 동일하게 읽게 되는 문장입니다.

4. 영어이름은 대문자로만 이루어집니다.

5. 답이 여러개인 경우 사전 순으로 앞에 있는 문장을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 문장의 대문자 각 숫자를 구한 뒤, 팰린드롬으로 재구성합니다.

 

3. "I'm Sorry Hansoo"와 재구성한 팰린드롬 문장 중 하나를 결과로 출력합니다. 

 

 

팰린드롬 구성.

 

대문자 글자의 개수가 홀수인 알파벳이 0개일 때

 

ABAB

A = 2개, B = 2개

"개수 ÷ 2"만큼 연속한 문장 : front (AB)

"개수 ÷ 2"만큼 연속한 문장의 반대 형태 : end(BA)

front + end = ABBA = 팰린드롬!

 

 

대문자 글자의 개수가 홀수인 알파벳이 1개일 때

 

ABABCCC

A = 2개, B = 2개, C = 3개

"개수 ÷ 2"만큼 연속한 문장 : front (ABC)

홀수 알파벳 : mid(C)

"개수 ÷ 2"만큼 연속한 문장의 반대 형태 : end(CBA)

front + mid + end = ABCCCBA = 팰린드롬!

 

대문자 글자의 개수가 홀수인 알파벳이 2개이상 일 때

 

ABABBCCC

A = 2개, B = 3개, C = 3개

"개수 ÷ 2"만큼 연속한 문장 : front (ABC)

홀수 알파벳 : mid(BC)

"개수 ÷ 2"만큼 연속한 문장의 반대 형태 : end(CBA)

front + mid + end = ABCBCCBA = 팰린드롬 X!

 

홀수 글자가 2개 이상이면 mid에서 팰린드롬의 형태를 만들 수 없습니다.

 

예제입력 3.

1. 입력된 정보를 저장합니다.

 

영어이름 : ABACABA

 

2. 문장의 대문자 각 숫자를 구한 뒤, 팰린드롬으로 재구성합니다.

 

알파벳 각 개수

A = 4개

B = 2개

C = 1개

홀수인 글자가 1개

 

"개수 ÷ 2"만큼 연속한 문장 : front (AAB)

홀수 알파벳 : mid(C)

"개수 ÷ 2"만큼 연속한 문장의 반대 형태 : end(BAA)

front + mid + end = AABCBAA = 팰린드롬!

 

3. "I'm Sorry Hansoo"와 재구성한 팰린드롬 문장 중 하나를 결과로 출력합니다. 

 

AABCBAA을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 이름에 사용된 대문자 알파벳의 개수를 구합니다.
• 알파벳 개수를 탐색하며 front, mid, end를 구성합니다.
• 홀수의 개수가 2개 이상이면 "I'm Sorry Hansoo"를 BufferedWriter 저장합니다.
• 팰린드롬을 만드는데 성공하였으면 팰린드롬을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main{
    static int[] alphabet = new int[26];	//알파벳 개수 저장 배열
    static StringBuilder sb = new StringBuilder();	//결과 저장할 StringBuilder
    static StringBuilder front = new StringBuilder();
    static StringBuilder end = new StringBuilder();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String name = br.readLine();
        boolean check = false;	//팰린드롬 만들 수 있는지 확인 변수
        int oddCheck = 0;		//알파벳 홀수인 개수
        char mid = '0';
        //알파벳 개수를 구하기
        for(int i=0;i<name.length();i++)
            alphabet[name.charAt(i) - 65]++;

        //팰린드롬 만들기
        for(int i=0;i< alphabet.length;i++){
            if(alphabet[i] != 0 && alphabet[i]%2 == 1){
                if(oddCheck==0){	//홀수가 1개가 될 때
                    oddCheck++;
                    mid = (char)('A' + i);	//mid구하기
                }else{	//홀수가 2개가 될 때
                    //팰린드롬 만들지 못하기 때문에 "I'm Sorry Hansoo"를 저장
                    sb = new StringBuilder("I'm Sorry Hansoo");
                    check = true;
                    break;
                }
            }
            //"개수 ÷ 2"만큼 front, end 구성 
            for(int j=0;j<alphabet[i]/2;j++){
                front.append((char)('A' + i));
                end.insert(0, (char)('A' + i));
            }
        }
        if(!check){		//팰린드롬 만들었을 때
            if(mid == '0')	//홀수 개수가 0개일 때
                sb.append(front).append(end);	//front + end
            else		//홀수 개수가 1개일 때
                sb.append(front).append(mid).append(end);	//front + mid + end
        }

        bw.write(sb.toString());		//팰린드롬 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}