[BOJ] 1254 : 팰린드롬 만들기 - java

문제

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

---

문제풀이

입력된 문자가 처음부터 팰린드롬인지 확인한다.
아닐 경우 반복하여 검사하며 팰린드롬 구조로 만드는 작업을 해야 한다.
앞부분 문자를 추출하여 뒤집고 뒷부분에 맞춘 후 팰린드롬인지 체크한다.
팰린드롬이 될 때까지 추출하는 앞 문자 개수를 늘려간다.

---

소스코드

import java.io.*;

public class _1254 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String S = br.readLine();
        int n = S.length();

        StringBuilder sb = new StringBuilder(S);
        if (sb.toString().equals(sb.reverse().toString())) {
            bw.write(n + "\n");
        } else {
            sb.reverse();
            for (int i = 1; i < n; i++) {
                String pre = S.substring(0, i);
                sb = new StringBuilder(S);
                sb.append(new StringBuilder(pre).reverse());

                if (sb.toString().equals(sb.reverse().toString())) {
                    bw.write(sb.length() + "\n");
                    break;
                }
            }
        }
        bw.flush();
    }
}

---

소스코드 - 최적화

import java.io.*;

public class _1254 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String S = br.readLine();
        int n = S.length();

        if (isPalindrome(S)) {
            bw.write(n + "\n");
        } else {
            int minLength = 2 * n - 1;
            for (int i = 1; i < n; i++) {
                if (isPalindrome(S, i)) {
                    minLength = n + i;
                    break;
                }
            }
            bw.write(minLength + "\n");
        }
        bw.flush();
    }
    
    private static boolean isPalindrome(String s) {
        int start = 0, end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

    private static boolean isPalindrome(String s, int offset) {
        int start = offset, end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

중복된 StringBuilder 사용 제거
회문을 검사할 때 StringBuilder 객체를 사용하지 않고, 대신 문자열의 인덱스를 사용하여 효율적으로 검사
메모리 사용 최소화
불필요한 객체 생성 없이, 문자열의 인덱스를 활용하여 회문 여부를 검사
시간 단축
가능한 빠르게 회문을 찾아내고 루프를 탈출

---

etc

알고리즘 분류 : 브루트포스 알고리즘

 

https://djun95.tistory.com/12

브루트포스 탐색 알고리즘