[Java] 회문 (펠린드롬 만들기)

문제를 풀기 위해 나눠야 할 갈래가 생각보다 많았다.

일단 현재 내가 푼 풀이방식과 코드가 상당히 마음에 들지 않는다. 체계적으로 정형화되어 있지 않고 주먹구구식 풀이 같은 느낌이랄까. 또 자바의 특징을 별로 살리지 못한 느낌이다. 정석적인 풀이법을 보고 싶다.

 

처음에는 입력받은 문자를 정렬 후 가장 앞에 있는 문자부터 비교해야 해서 선입선출 PriorityQueue에 저장해서 풀어봤지만 여러 가지 변수가 많아서 적합하지 않아 배열에 저장 후 sort 시킨 다음에 index를 증가시키면서 비교하는 방법을 사용했다.

 

 

 

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

1213번: 팰린드롬 만들기

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static StringBuilder sb;
    static String[] strArray;

    public static void main(String[] args) throws IOException {

        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        strArray = br.readLine().split("");

        Arrays.sort(strArray);

        pelin();

    }

    public static void pelin(){

        String hidden = null; 
        //입력받은 문자열이 홀수라면 홀수로 존재해도 상관없는 문자가 있기 때문에 
        //그 문자를 저장해두는 변수
        boolean check= false;

        for(int i=0; i< strArray.length-1; i+=2) {

            if (strArray[i].equals(strArray[i + 1])) {
                if (i == 0) { //처음 추가 한다면
                    sb.append(strArray[i]);
                    sb.append(strArray[i]);

                    continue;
                }
                sb.insert(sb.length() / 2, strArray[i]); //문자열의 중간에 삽입
                sb.insert(sb.length() / 2, strArray[i]);
            } else {
                if (check == false && strArray.length % 2 == 1) { 
                //입력받은 문자열이 홀수이면서 hidden 문자가 없을 때
                    hidden = strArray[i];
                    check = true;

                    for(int j = i+1; j<strArray.length-1; j+=2){ 
                    //hidden이 있다면 index 순서가 하나씩 밀리므로
                        if (strArray[j].equals(strArray[j + 1])) {
                            sb.insert(sb.length() / 2, strArray[j]);
                            sb.insert(sb.length() / 2, strArray[j]);
                        }
                        else {
                            System.out.println("I'm Sorry Hansoo");
                            return;
                        }
                    }
                    sb.insert(sb.length()/2, hidden);
                    System.out.println(sb);
                    return;

                } else {
                    System.out.println("I'm Sorry Hansoo");
                    return;
                }
            }
        }
        
        if(strArray.length %2 ==1) { 
        //입력받은 문자열이 홀수라면 마지막 문자를 따로 추가시켜 주어야함
            sb.insert(sb.length()/2, strArray[strArray.length-1]);
        }
        System.out.println(sb);
    }
}

 

1. 입력받은 문자열을 한 문자씩 나누어 배열 strArray에 저장

 

2. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력해야 하기 때문에 배열 strArray를 정렬

 

3. 인덱스를 2씩 증가시키면서 현재 가리키는 인덱스의 문자와 그다음 인덱스의 문자를 비교

 

4. 문자가 서로 같다면 StringBuilder sb에 insert (여기서 맨 처음에는 append를 하고 그다음부터는 sb의 중앙 인덱스에 insert)

 

 

입력받은 문자열이 홀수일 때 고려해야 할 점

• 단 하나의 문자는 홀수개로 존재해도 회문이 가능하다!
• 인덱스를 2씩 증가시키기 때문에 마지막 문자를 처리해주어야 한다.