palindrome

Algorithm/Baekjoon Online Judge
[Java] 백준 1509 (팰린드롬 분할) Gold 1
Problem : https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net Approach 주어진 문자열이 최소 몇 개의 팰린드롬 문자열로 구성되어 있는지를 구하는 문제이다. 팰린드롬 문자열 자체를 구하는 로직은 O(n^2) 의 시간복잡도를 가진다. 팰린드롬 문자열을 구하는 방법은 투포인터를 사용하였다. DP[i] 는 0 ~ i인덱스의 문자열이 몇 개의 최소 팰린드롬 문자열로 구성되는지..
→2021.04.16
Algorithm/Programmers
[java] 프로그래머스 (가장 긴 팰린드롬) Level 3
Problem : https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr Approach 처음 생각한 풀이는 문자열의 왼쪽 끝과 오른쪽 끝을 각각 left와 right로 정해놓고, 범위를 점점 줄여나가는 식으로 풀이를 생각했지만, 결과적으로 시간초과가 나는 코드가 됐다. 문자열의 모든 위치를 기준으로 시작하여, 팰린드롬이면 계속해서 범위를 늘려 팰린드롬 문자열인지..
→2021.02.13

• 이전
• 1
• 다음