[JAVA] 10942 팰린드롬?

안녕하세요. 

 

날이 요즘 참 덥네요. 지구온난화 때문일까요. 

 

오늘의 문제는

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

팰린드롬을 보니 옛날 슈퍼주니어 노래 중 로꾸거 가 생각이 납니다. 수박이박수 이런 가사였던 것 같은데. 이제는 끔찍한 코딩문제가 되어 돌아왔습니다. 

 

 

<나의 풀이> 

 

우선 주어진 범위가 팰린드롬인지 아닌지를 확인하기 위해서는 어떤 방법을 사용할까부터 생각을 해봤습니다.

특별한 방법을 생각해 봤는데, 특별한 생각이 들지 않아서 결국 직접 하나하나 확인을 하기로 했습니다.

 

수열의 크기(N)은 2,000으로 괜찮은데, 홍준이가 내는 문제의 수(M)가 (1,000,000,000) 참 많군요. 홍준아..

시간초를 보니 JAVA는 2.5초로 홍준이의 호기심을 만족하기 위해서는 하나의 답을 구하는데 O(n)도 안될 것 같습니다.

 

그래서 메모지에이션을 사용하기로 하였습니다. 

 

보통 한번에 모든 경우의 페린드롬을 확인하고 저장하는데, 저는 매 문제마다 팰린드롬을 확인하며 그 과정을 저장했습니다. 

1. solution(int s, int e)

문제의 범위를 받아 범위가 짝수인지 홀수인지 판단하는 메서드

 

2. caseOfEven(int s, int e)

범위가 짝수인경우 팰린드롬을 확인하며 그 과정을 저장하는 메서드

 

3. caseOfOdd(int s, int e)

범위가 홀수인경우 팰린드롬을 확인하며 그 과정을 저장하는 메서드

 

 이게 제 풀이인데..그 비교 시작점을 구지구지 중간에서 시작을 하지 않고 처음과 끝에서 시작하면 홀수 짝수 경우를 나눌 필요가 없었군요... 바보

또 각 문제마다 직접 구하는 것도 물론 좋지만, 수열의 크기(N)를 보고 2001 x 1000 = 2,000,000 정도 경우가 존재하니 모든 케이스를 그냥 O(N)으로 구하자!라고 다음에는 생각을 했으면 좋겠습니다.

 

<코드>

// 코드 1
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Num10942 {
    static int n;
    static int[] arr;
    static int[][] memo;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        arr = new int [n+1];
        memo = new int[n+1][n+1];
        for(int i=1; i<=n;i++){
            Arrays.fill(memo[i],-1);
        }
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(solution(s,e)+"\n");
        }
        System.out.print(sb);
    }
    public static String solution(int s, int e){
        if(s==e){
            return "1";
        }
        if(memo[s][e]!=-1){
            return String.valueOf(memo[s][e]);
        }
        if((s+e)%2==0){
            caseOfEven(s,e);
        }else{
            caseOfOdd(s,e);
        }
        return String.valueOf(memo[s][e]);
    }
    public static void caseOfEven(int s, int e){
        boolean isTrue = true;
        int ns = ((s+e)/2)-1;
        int ne = ns+2;
        while(ns>0 && ne<=n){
            if(!isTrue){
                memo[ns][ne] = 0;
                ns--;
                ne++;
                continue;
            }
            if(arr[ns]==arr[ne]){
                memo[ns][ne] = 1;
            }else{
                isTrue = false;
                memo[ns][ne] = 0;
            }
            ns--;
            ne++;
        }
    }
    public static void caseOfOdd(int s, int e){
        boolean isTrue = true;
        int ns = (s+e-1)/2;
        int ne = (s+e+1)/2;
        while(ns>0&&ne<=n){
            if(!isTrue){
                memo[ns][ne] = 0;
                ns--;
                ne++;
                continue;
            }
            if(arr[ns]==arr[ne]){
                memo[ns][ne] = 1;
            }else{
                isTrue = false;
                memo[ns][ne] = 0;
            }
            ns--;
            ne++;
        }
    }
}

 

<후기>

1. 뭔가 포스팅 방식을 살짝 바꾸고 싶다. 그래서 써본 메서드 나열. 

2. 점화식을 사용하지 않은 디피.

3. 디피는 점화식이 아니고 메모지에이션이 아닐까

 

<피드백>

제 코드가 그럴듯 하지 않아서 새로 또 구현을 해봤습니다. 

이번에는 

1. 모든 경우를 확인한다 (fidnPelindrome) 

 

2. 3이상의 길이를 가진 범위의 팰린드롬을 확인한다 (isPelindrom) 

// 코드 2
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Num10942 {
    static int n;
    static int[] arr;
    static int[][] memo;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        arr = new int [n+1];
        memo = new int[n+1][n+1];
        for(int i=1; i<=n;i++){
            Arrays.fill(memo[i],-1);
        }
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        findPelindrome();
        int m = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(memo[s][e]+"\n");
        }
        System.out.print(sb);
    }
    public static void findPelindrome(){
        for(int i=1; i<=n;i++){
            for(int j=1; j<=n; j++){
                if(i==j){
                    memo[i][j] = 1;
                    continue;
                }
                if(i+1==j){
                    if(arr[i]==arr[j]){
                        memo[i][j] = 1;
                    }else{
                        memo[i][j] = 0;
                    }
                    continue;
                }
                if(isPelindrome(i,j)){
                    memo[i][j] = 1;
                }else{
                    memo[i][j] = 0;
                }
            }
        }
    }
    public static boolean isPelindrome(int i, int j){
        while (i<j){
            if(arr[i] != arr[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

확실히 코드는 간단해졌습니다. 변수와 메서드가 줄어들다보니 확실히  메모리에서도 더 좋은 결과를 보여줬습니다. 

하지만 시간은 더 오래 걸렸습니다. 그 원인은 비교 시작점의 차이떄문입니다. 

 

팰린드롬의 특성상 가운데 부터 나아가면 길이가 n인 수열에서 n/2 만큼의 경우를 한번에 확인하면서 올 수 있기 때문입니다. 그래서!! 이를 적용해보았습니다.

 

//코드 3
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Num10942 {
    static int n;
    static int[] arr;
    static int[][] memo;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        arr = new int [n+1];
        memo = new int[n+1][n+1];
        for(int i=1; i<=n;i++){
            Arrays.fill(memo[i],-1);
        }
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        findPelindrome();
        int m = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(memo[s][e]+"\n");
        }
        System.out.print(sb);
    }
    public static void findPelindrome(){
        for(int i=1; i<=n;i++){
            for(int j=1; j<=n; j++){
                if(memo[i][j] != -1){
                    continue;
                }
                if(i==j){
                    memo[i][j] = 1;
                    continue;
                }
                if(i+1==j){
                    if(arr[i]==arr[j]){
                        memo[i][j] = 1;
                    }else{
                        memo[i][j] = 0;
                    }
                    continue;
                }
                isPelindrome(i,j);
            }
        }
    }
    public static void isPelindrome(int i, int j){
        int lp, rp;
        if((i+j)%2==0){
            lp=((i+j)/2)-1;
            rp= lp+2;
        }else{
            lp = ((i+j)/2);
            rp = lp+1;
        }
        boolean pelindromeCheck =true;
        while (lp>=i && rp<=j){
            if(!pelindromeCheck){
                memo[lp][rp] = 0;
                lp--;
                rp++;
                continue;
            }
            if(arr[lp] != arr[rp]){
               memo[lp][rp] = 0;
               pelindromeCheck = false;
               lp--;
               rp++;
               continue;
            }
            memo[lp][rp]= 1;
            lp--;
            rp++;
        }
    }
}

 

위에서 부터 코드 3, 2, 1