[BOJ21925] 짝수 팰린드롬(그리디, 탐욕 알고리즘)알고리즘/탐욕(그리디)2023. 10. 6. 21:27
Table of Contents
반응형
문제링크
https://www.acmicpc.net/problem/21925
문제풀이
그리디 알고리즘 풀이 방법을 알게 되어 풀이시
메모리와 시간적 측면에서 앞서 직접 DP 풀이한 방식보다 나은 것을 확인가능했다.
- 그리디 알고리즘 풀이
- 핵심 아이디어 : 큰 짝수 팰린드롬은 작은 짝수 팰린드롬으로 구성이 된다.
그러므로
1) i와 j 포인터를 사용해서 최소가 되는 짝수 팰린드롬 구하면 결과값 증가시키고 포인터 이동 (i < N까지)
2) i 시작점에서 팰린드롬을 찾지 못하는 경우 종료 후 -1 출력
(투 포인터 방식)
제출코드
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();
}
}
반응형
'알고리즘 > 탐욕(그리디)' 카테고리의 다른 글
프림 알고리즘(최소신장트리, MST, prime) (0) | 2023.09.23 |
---|---|
크루스칼 알고리즘 (MST, 최소 신장 트리, kruskal) (0) | 2023.09.23 |
[BOJ2887] 행성 터널(최소신장트리,MST, 크루스칼 알고리즘) (0) | 2023.09.22 |
[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) (0) | 2023.09.07 |
[BOJ1368] 물대기 (프림 알고리즘, 최소 신장 트리, 그리디) (0) | 2023.09.06 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!