백준 1254번) 팰린드롬 만들기 (JAVA)

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

1254번: 팰린드롬 만들기

#문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

 

#알고리즘

• 문자열
• 부루트포스 알고리즘

#난이도

Silver 1

 

#풀이방법

부르트포스 알고리즘은 코테에 등장하는 1순위 유형이다. 남들은 쉬운 유형이라고는 하지만 내게는 dp만큼 어렵고 까다로운 알고리즘이다. (내가 너무 그래프에 익숙해져있어서 그런가??)

 

암튼 본론으로 들어가면, 문제에서 지정된 문자열이 있고, 우린 여기서 0개 이상의 단어를 추가하여

팰린드롬인지 확인을 하면 된다.

 

유형이 부르트포스이기 때문에 모든 글자를 하나 하나씩 확인해보는 방법을 적용하였다.

 

하지만 여기서 처음 탐색 idx를 문자열의 첫번째 글자가아닌 문자열의 중간부터 탐색하여 끝까지 가도록 하였다. 

그 이유는 팰린드롬의 특성상 중간을 기준으로 좌우가 대칭이기 때문에 중간을 처음 시작 인덱스로 잡고 

오른쪽으로 문자열 끝을 넘을때까지 while문을 돌려 최솟값을 업데이트 해준다.

 

여기서 중요한 것은 탐색 유형을 2가지로 나누는 것인데, 

예를 들어 문자열이 aba 인경우가 있고 abba 인경우가 있다.

 

ex1) aba인 경우는 중간 인덱스인 b를 기준으로 양끝으로 탐색하여 맞는지 확인하는 방법이고,

 

ex2) abba는 기준점이 없고, 두개의 중간 위치인  bb를 기준으로 양끝으로 가는 것이기 때문에

 

1번 ex와 2번 ex의 방법 모두 적용 시켜야 한다.

 

여기서 최솟값 int min은 주어진 문자열이 좌우 대칭이 없는 경우 문자열 끝을 기준으로 왼쪽에 있는 문자열들을

오른쪽에 추가하면 되기 때문에 결국 int min = (문자열의 길이-1)*2+1이 된다.

 

 

//ex2)인경우 aba
            int start_idx = idx;//오른쪽 방향으로 탐색하는 인덱스
            int prior_idx = idx-1;//왼쪽 방향으로 탐색하는 인덱스
 
            while(start_idx < str.length() && -1 < prior_idx && str.charAt(prior_idx) == str.charAt(start_idx)) {
                        
                start_idx++;
                prior_idx--;
                        
            }//start_idx와 prior_idx와 문자열의 길이 범위 안에 있을 경우, 
             // 범위를 지정하지 않을경우  StringIndexOutOfBoundsException이 일어난다.
            
            
            if(start_idx == str.length()) {
                
                min = Math.min(min, str.length()+prior_idx+1);
            
            }

 

위에 코드는 ex2)의 예를 나타낸 경우인데,

오른쪽으로 가는 start_idx와 왼쪽으로 가는 prior_idx를 따로 선언하여 문자열의 길이 범위 안에 있을때 2개의 글자가 ㅇ리치할경우, 계속 좌우로 탐색을 진행한다. 그러다가 start_idx가 문자열 끝에 도달 할 경우

Math.min메소드를 이용하여 기존 문자열의 길이 + 왼쪽으로 끊긴 부분의 prior_idx +1를 하여 min값을 업데이트 시킨다. 

 

            start_idx = idx+1;
            prior_idx = idx-1;
                
            while(start_idx < str.length() && -1 < prior_idx && str.charAt(prior_idx) == str.charAt(start_idx)) {
                
                prior_idx--;
                start_idx++;
                
            }
                
            if(start_idx == str.length()) {
                    
                min = Math.min(min,str.length()+prior_idx+1);
            }

 

ex1)의 경우도 시작 위치만 다를 뿐이지 ex1)과 동일하게 탐색하여 min값을 업데이트 시켜준다.

 

 

#전체 코드

 

import java.util.*;
//1t
 
 
public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String str = sc.next();//문자열 입력
        
        int idx = str.length()/2;//중간부터 탐색
        
        int min = (str.length()-1)*2+1;//추가해야하는 최대 글자
        
        
        while(idx != str.length()){
            //기준점 idx가 끝에 도달하기까지에 대한 루프
            
            //ex2)인경우 aba
            int start_idx = idx;//오른쪽 방향으로 탐색하는 인덱스
            int prior_idx = idx-1;//왼쪽 방향으로 탐색하는 인덱스
 
            while(start_idx < str.length() && -1 < prior_idx && str.charAt(prior_idx) == str.charAt(start_idx)) {
                        
                start_idx++;
                prior_idx--;
                        
            }//start_idx와 prior_idx와 문자열의 길이 범위 안에 있을 경우, 
             // 범위를 지정하지 않을경우  StringIndexOutOfBoundsException이 일어난다.
            
            
            if(start_idx == str.length()) {
                
                min = Math.min(min, str.length()+prior_idx+1);
            
            }
 
            
            
            //ex1)인경우 abba
            
            start_idx = idx+1;
            prior_idx = idx-1;
                
            while(start_idx < str.length() && -1 < prior_idx && str.charAt(prior_idx) == str.charAt(start_idx)) {
                
                prior_idx--;
                start_idx++;
                
            }
                
            if(start_idx == str.length()) {
                    
                min = Math.min(min,str.length()+prior_idx+1);
            }
                
                
            idx++;//기준값 업데이트
        }
        
        
        System.out.println(min);
        
    }
 
}