Java #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;

    }

}

Colored by Color Scripter

cs

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

https://github.com/doorBW/algorithm_practice