알고리즘/백준

BOJ) 팰린드롬? (10942, JAVA)

Zin0_0 2020. 8. 25. 17:49
반응형

팰린드롬?

 

10942번: 팰린드롬?

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

www.acmicpc.net

 

풀이

 

효율적이지 않은 코드지만, 왠만한 팰린드롬 문제는 다 통과될 수 있도록 코드를 작성했다.

검사할 글자의 개수가 홀수일 때는 중앙점을 기준으로 좌 우로 -1, +1을 각각 해주면서 비교해주면 된다.짝수인 경우에는 중앙이 left가 되고, 중앙+1을 right로 비교해주면 된다.따라서, 위의 조건에 따라 짝수인 경우에는 left를 mid로 설정해주는 것을 예외처리 해줘서, left와 right가 같은지 확인할 수 있도록 했다.

 

코드

 

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

public class Main {
    final static String Palindrome = "1", NoPalindrome = "0", NewLine = "\n";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] numArr = new int[size];

        for(int i=0; i<size; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }

        int testCases = Integer.parseInt(br.readLine());
        int[][] testCaseArr = new int[testCases][2];

        for(int i=0; i<testCases; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<2; j++) testCaseArr[i][j] = Integer.parseInt(st.nextToken())-1;
        }
        br.close();

        solution(numArr,testCaseArr);
    }

    private static void solution(int[] numArr, int[][] testCaseArr) {
        StringBuffer sb = new StringBuffer();
        for(int[] testCase : testCaseArr)   sb.append(isPalindrome(numArr, testCase)).append(NewLine);

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

    private static String isPalindrome(int[] numArr, int[] testCase) {
        if(testCase[0] == testCase[1])  return Palindrome; 
        
        int mid = (testCase[0] + testCase[1]) /2;
        int left = mid-1, right = mid+1;
        if((testCase[0]+testCase[1]) %2 !=0)    left++;

        while(left >= testCase[0]) {
            if(numArr[left--] != numArr[right++])   return NoPalindrome;
        }

        return Palindrome;
    }
}
반응형