[BOJ21925] 짝수 팰린드롬(그리디, 탐욕 알고리즘)

 

 

---

문제링크

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

21925번: 짝수 팰린드롬

---

문제풀이

그리디 알고리즘 풀이 방법을 알게 되어 풀이시
메모리와 시간적 측면에서 앞서 직접 DP 풀이한 방식보다 나은 것을 확인가능했다.

- 그리디 알고리즘 풀이

- 핵심 아이디어 : 큰 짝수 팰린드롬은 작은 짝수 팰린드롬으로 구성이 된다.

 

그러므로

1) i와 j 포인터를 사용해서 최소가 되는 짝수 팰린드롬 구하면 결과값 증가시키고 포인터 이동 (i < N까지)

2) i 시작점에서 팰린드롬을 찾지 못하는 경우 종료 후 -1 출력

(투 포인터 방식)

 

---

제출코드

위가 그리디 알고리즘 풀이, 아래가 dp 풀이

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

public class Main {
    
    static int N;
    
    static int[] data;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        data = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

    }

    static boolean isEvenPalindrome(int i, int j) {
        if(j - i + 1 % 2 == 1) return false; // 짝수 범위가 아닌 경우
        for(int k = 0; k <= (j - i) / 2; k++) { // 팰린드롬 여부 확인
            if(data[i + k] != data[j - k]) return false;
        }

        return true;
    }

    static void pro() throws IOException {
        int result = 0;
        int i = 1;
        int j = 0;
        while(i < N) {
            boolean find = false;
            for(j = i + 1; j <= N; j += 2) { 
                if(isEvenPalindrome(i, j)) {
                    find = true;
                    result += 1;
                    break;
                }
            }

            if(!find) {
                result = -1;
                break;
            }

            i = j + 1;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}