TigerCow.Door

'자바 가장 긴 팰린드롬'에 해당되는 글 1건

안녕하세요. 문범우입니다.

이번 포스팅에서는 Java 언어를 통해서 '가장 긴 팰린드롬' 이라는 알고리즘 풀이를 풀어보도록 하겠습니다.

해당 문제는 아래 프로그래머스 사이트에서 풀어보실 수 있습니다.


https://programmers.co.kr/learn/courses/30/lessons/12904?language=java



1. 문제 접근


팰린드롬이란, 문자열을 거꾸로 뒤집었을때도 모양이 같은 것들을 말합니다.

예를 들어, 'aba', 'aaddaa' 등도 팰린드롬이며 'asddfd' 라는 문자열에서는 'dfd'가 팰린드롬 문자열입니다.


해당 문제는 입력으로 주어지는 문자열에서 길이가 가장 긴 팰린드롬을 찾아서 그 길이를 반환하는 문제입니다.


팰린드롬에 대한 자세한 설명은 문제 또는 구글링을 통해 확인하실 수 있습니다.


먼저, 팰린드롬 문자열은 그것이 홀수 길이 이거나 짝수 길이 일때로 나누어서 생각해볼 수 있습니다.

팰린드롬 문자열이 홀수 길이 일때에는, 하나의 문자열을 기준으로 잡아서 그 왼쪽과 오른쪽 문자열을 서로 비교해가며 구하면됩니다.

팰린드롬 문자열이 짝수 길이 일때에는, 연속으로 동일한 문자열 2개를 기준으로 잡아서 그 왼쪽과 오른쪽 문자열을 서로 비교해가며 구하면됩니다.


하지만 중요한건, 우리는 입력되는 문자열에 대해서 계산될 팰린드롬 문자열의 길이가 홀수인지 짝수인지 미리 알 수 없습니다.

따라서, 입력되는 문자열에 대해 홀수 길이에 대한 알고리즘과, 짝수 길이에 대한 알고리즘을 모두 통과시키도록 하고 여기서 더 큰 값을 반환하도록 해야 합니다.



2. Java 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution
{
    public int solution(String s)
    {
        int max_len = 1;
        int temp_len = 1;
        int len = s.length();
        // 팰린드롬 길이가 짝수일 경우
        for(int i=0; i<len-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){ // 짝수 문자열에서 팰린드롬 기준점 선출
                temp_len = 0;
                for(int j=i+1; j<len; j++){
                    try{
                        char left = s.charAt(i+1-j+i); // left 위치선정
                        // left 위치 선정은 약간 까다로울 수 있음.
                        // 직접 연습장에 예시를 하나 두고 i와 j값을 변화시키며 확인해보는 것이 좋음
                        char right = s.charAt(j);
                        if(left == right){
                            temp_len += 2;
                        }else{
                            break;
                        }
                    }catch(Exception e){
                        break;
                    }
                }
            }
            if(max_len < temp_len){
                max_len = temp_len;
            }
        }
        // 팰린드롬 길이가 홀수일경우
        for(int i=0; i<len-1; i++){
            temp_len = 1;
            for(int j=i-1; j>=0; j--){
                try{
                    char left = s.charAt(j);
                    char right = s.charAt(i+i-j); // right 위치선정
                    // 이 또한 직접 예시를 하나 두고 i와 j값을 변화시키며 확인해보는 것이 좋음
                    if(left == right){
                        temp_len += 2;
                    }else{
                        break;
                    }
                }catch(Exception e){
                    break;
                }
            }
            if(max_len < temp_len){
                max_len = temp_len;
            }
        }
        return max_len;
    }
}
cs


해당 코드는 아래 github 주소에서도 만나보실 수 있습니다.

https://github.com/doorBW/algorithm_practice

'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요