알고리즘/백준
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;
}
}
반응형