[백준] [1259] 팰린드롬수

문제

어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다.

수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다.

출력

각 줄마다 주어진 수가 팰린드롬수면 'yes', 아니면 'no'를 출력한다.

 

package algorithm;

import java.util.Scanner;

public class 팰린드롬수_1259 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		while(true) { // 0이 입력될때까지
			String str = sc.nextLine();
			int num = Integer.parseInt(str);
			if(num == 0) break;
			
			// 숫자의 최대길이
			int limit = str.length()-1;
			
			// 팰린드롬인지 체크
			boolean flag = true;
			
			for(int i=0;i<=(limit/2);i++) {
				// 맨처음과 맨뒤부터 동시에 인덱스를 좁히며 탐색
				if(str.charAt(i) != str.charAt(limit-i)) {
					flag = false;
					System.out.println("no");
					break;
				}
			}
			if(flag) {
				System.out.println("yes");
			}
		}
	}
}

 

오랜만에 풀어보는 팰린드롬수 글쓴이도 이 수를 참 재밌다고 생각한다. 앞으로 읽어도 뒤로 읽어도 같은 수라 참 호감이 간다.

팰린드롬의 여부를 확인하기위해서는 입력값을 숫자로 생각하기보다는 문자열로 생각하며 문제에 접근해야한다.

단순히 문자열의 앞뒤 값을 비교하며 중앙 인덱스로 점차 이동하면서 비교하면 되는 문제이다.

 

arr = [1][2][3][4][1]

이런 배열이 존재할때, arr[0] == arr[4]를 비교하고 맞다면 다음으로 arr[1] == arr[3]을 비교하면 되는 간단한 문제이다.

가운데는 굳이 확인할 필요가 없기 때문에 int limit = arr.length-1을 담아 limit/2 만큼 확인하도록 하였다.

 

for(int i = 0; i < (limit/2); i++) 로직은

기준값 arr[0] == arr[4]는 결국 arr[4] == arr[0]과 같기 때문에 중간의 인덱스까지만 반복해준 것이다.

 

위의 문제는 총 숫자의 길이가 5자밖에 되지 않기 때문에 하지 않아도 되는 로직이지만

만약, 문자열의 길이가 999999이거나 1000000인 문자열이 팰린드롬인지 확인할때 반복문을 100만번 탐색하는 것과 

50만번 탐색하는 것의 시간복잡도는 크게 차이날 수 있다.