package programmers;
class 가장_긴_팰린드롬_Java_230917{
/*
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.
제한사항
문자열 s의 길이 : 2,500 이하의 자연수
문자열 s는 알파벳 소문자로만 구성
*/
public int solution(String s) {
int length = s.length();
// 문자열의 길이가 1 이하인 경우, 그대로 길이를 반환한다.
if (length <= 1) return length;
// dp[i][j] 배열을 사용하여 팰린드롬 부분 문자열 여부를 저장한다.
boolean[][] dp = new boolean[length][length];
int maxPalidrome = 1; //1인 부분 문자열이 팰린드롬일 경우는 기본값으로 둔다.
// 초기값: 모든 길이가 1인 부분 문자열은 팰린드롬이다.
for (int i = 0; i < length; i++) {
dp[i][i] = true;
}
// 길이가 2인 부분 문자열을 검사한다.
for (int i = 0; i < length - 1; i++) { // +1을 체크할 것이므로 length - 1까지만 검사한다.
if (s.charAt(i) == s.charAt(i + 1)) { //길이가 2일 경우에는 앞 뒤가 같으면 팰린드롬이다.
dp[i][i + 1] = true;
// 만약 길이가 2인 팰린드롬을 찾으면 최대 길이를 2로 갱신해 놓는다.
maxPalidrome = 2;
}
}
// 길이가 3 이상인 부분 문자열을 검사한다.
for (int len = 3; len <= length; len++) { //길이가 3인 부분 문자열부터 검사한다.
for (int i = 0; i + len - 1 < length; i++) {
int j = i + len - 1; // j는 i에서 길이를 더한 값이다.
// 문자열의 양 끝이 같고, 내부 부분이 팰린드롬인 경우 팰린드롬으로 표시한다.
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
// 현재 팰린드롬의 길이를 갱신해 놓는다.
maxPalidrome = len;
}
}
}
return maxPalidrome;
}
}
yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환 2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...
댓글
댓글 쓰기