[JAVA] 백준 10942번 : 팰린드롬?

 

---

 

 

• 코드

실패 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

               int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		String string = br.readLine().replace(" ","");  //==>>>여기가 런타임의 원인??(추측)
		
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0;i<M;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			System.out.println(isPalindrome(Integer.parseInt(string),a,b));  //==>>여기가 시간초과의 원인
		}

	}
	
	static int isPalindrome(int number,int a, int b) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int temp = (b-a)/2+a;
		for(int i=a-1;i<=temp;i++) {
			if(integerToCharArray[i] != integerToCharArray[--b]) 
				return 0;
		}
		return 1;
	}
}

 

 

 

성공 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

               ==>> int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

               시간초과는 반복문안에서 바로바로 출력을 해줬는데, 출력을 하는사이 작업을 하지 못해서? 그런 듯해서

               StringBuilder로 받아온 값을 append 시킨다음 반복문 빠져나온 뒤 한꺼번에 출력해주었다.

               결과는 맞았습니다!!

               

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] palindrom = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) 			
			palindrom[i] =  Integer.parseInt(st.nextToken());
		
				
		int M = Integer.parseInt(br.readLine());
		StringBuilder result = new StringBuilder();
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			
			result.append(isPalindrome(palindrom,
					Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())) +  "\n");
		}

		System.out.println(result.toString());
	}
	
	static int isPalindrome(int[] palindrom,int a, int b) {
		int temp = (b-a)/2 + a;
		for(int i=a;i<=temp;i++) {
			if(palindrom[i] != palindrom[b--]) 
				return 0;
		}
		return 1;
	}
}

 

 

다른 사람 코드 : 시간이 나보다 2배는 빠르게 나온다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int list[];
    static boolean check[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        list= new int[n+1];
        check =new boolean[n+1][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            list[i] = Integer.parseInt(st.nextToken());
        }

        solve();
        int q = Integer.parseInt(br.readLine());
        for(int i=0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int start =Integer.parseInt(st.nextToken());
            int end =Integer.parseInt(st.nextToken());
            if(check[start][end]){
                sb.append(1+"\n");
            }else{
                sb.append(0+"\n");
            }
        }

        System.out.println(sb.toString());


    }
    public static void solve(){
        for(int i=1; i<=n; i++){
            check[i][i] = true;
        }

        for(int i=1; i<n; i++){
            if(list[i]==list[i+1]){
                check[i][i+1] = true;
            }
        }

        for(int i=2; i<n; i++){
            for(int k=1; k<=n-i; k++){
                if(list[k]==list[k+i] && check[k+1][k+i-1]){
                    check[k][k+i] = true;
                }
            }
        }

    }
}