프로그래밍의 일부 문제는 고전적인 문제입니다. 일반적으로 이러한 작업은 수학과 관련이 있으며 컴퓨터 과학 전공 학생들과 면접에서 구직자에게 묻는 것을 매우 좋아합니다. 그것들은 당신의 생각을 프로그래머 방식으로 설정하고 그것을 훈련시키는 데 도움이 되기 때문에 좋습니다. 이러한 문제 중 하나는 문자열이 회문인지 여부를 확인하는 것이며 이 기사에서 이를 고려할 것입니다.
회문이란 무엇이며 회문을 찾을 수 있는 이유
회문은 숫자, 문자 조합, 단어 또는 텍스트가 양방향으로 동일하게 읽히는 것입니다. 요약하면, 회문은 중심이 대칭인 모든 문자 집합이라고 할 수 있습니다. 이 단어는 문자 그대로 "뒤로 달려가다"(palin은 "다시, 뒤로", dromos는 "달리다")에서 파생된 그리스어 어근에서 유래했습니다. 자바에서 Palindrome은 일반적인 의미와 동일합니다. 회문의 예:
1881년
아쿠쿠카
팝
정오
수준
로테이터
내 체육관
부인 저는 아담입니다
이제 전쟁에서 승리했습니다!
1881은 팰린드롬 숫자이고 나머지는 팰린드롬 문자열입니다. 이 기사에서는 문자열로 표현되는 회문을 살펴보겠지만 일부 알고리즘은 Java의 다른 종류의 회문에도 적용할 수 있습니다. 회문을 찾는 이유는 무엇입니까? 사실 우리는 일상생활에서 자주 회문을 찾을 필요가 없습니다. 매우 구체적인 작업입니다. 문자열 알고리즘을 기억한다면 실제로 더 자주 프로그래머는 회문이나 숫자를 검색하지 않고 문자열에서 하위 문자열을 검색할 수 있습니다. 그러나 회문과 관련된 문제에는 중요한 응용 프로그램이 있습니다. 첫 번째는 올림피아드 프로그램입니다. 회문을 식별하는 작업이 있을 수 있습니다. 초보 프로그래머와 관련된 두 번째 응용 프로그램은 인터뷰입니다. 기술 면접에서, 문자열이 회문인지 확인하는 프로그램을 빨리 작성하라는 요청을 받을 수도 있습니다. 음, 과학에서 회문을 찾는 가장 실용적인 응용은 생물학적 알고리즘입니다. Wikipedia에 따르면 생물학적 화합물의 회문성은 다양한 생물학적 화합물의 특성에 중요한 역할을 합니다.
Palindrome 알고리즘 코드 예제
생각 해봐. 문자열은 일련의 문자, 즉 문자 배열이라고 할 수 있습니다. 이 순서를 양쪽에서 중간으로 따라가면서 극단적인 캐릭터를 비교하는 것이 가장 논리적일 것입니다. 중앙에 도달할 때까지 모든 문자가 일치하면 회문이 있는 것입니다. String이 palindrome인지 확인하기 위해 boolean 메서드 validPalindrome(String s)를 만들어 봅시다. 자바 코드는 다음과 같습니다.
public class PalindromeTest1 {
//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
기본 메서드에서 회문 문자열 "level", "cool", "Madam" 및 "Now, sir, a war is won!"을 확인합니다. 보시다시피 첫 번째, 세 번째, 네 번째는 회문이지만 두 번째는 회문이 아닙니다. 프로그램은 무엇을 제공합니까?
수준은 회문입니까? 팰린드롬이 멋진가요? false 부인은 회문입니까? 거짓은 이제 전쟁에서 승리했습니다! 회문? 거짓
따라서 첫 번째는 회문이고 두 번째는 그렇지 않습니다. 그러나 세 번째와 네 번째는 무엇이 잘못되었습니까? 왜 결과가 거짓 입니까 ? 이 문자열의 일부 문자는 대문자이고 일부는 소문자이며 Java M과 m은 서로 다른 두 문자라는 점을 이미 짐작하셨을 것입니다. 이 차이를 고려하여 프로그램을 개선해 봅시다. 다음은 문자열이 대문자와 소문자 문제를 해결하는 회문인지 확인하는 프로그램입니다.
public class PalindromeTest2 {
//lowercase and uppercase characters should be treated the same:
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
이번에는 결과가 더 예측 가능합니다.
수준은 회문입니까? 팰린드롬이 멋진가요? false 부인은 회문입니까? 사실입니다. 이제 전쟁에서 승리했습니다! 회문? 거짓
음… 정확하게 예측할 수는 없습니다. "Madam"의 상황은 나아지고 있지만 길고 행복한 회문 "이제 전쟁이 승리했습니다!"는 어떻습니까? 모든 공백과 구두점 기호가 Java의 문자와 동일하다는 것을 기억한다면 매우 쉽습니다. 따라서 이러한 실수를 바로잡기 위해 알고리즘을 다시 개선해야 합니다. 공백과 구두점을 무시하도록 프로그램을 가르치자. 간단히 말해서 영숫자가 아닌 모든 문자를 무시합니다. 다음은 Java에서 개선된 회문 프로그램입니다.
public class PalindromeTest3 {
//in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
private static boolean isAlphanumeric(char c) {
return Character.isAlphabetic(c) || Character.isDigit(c);
}
public static boolean validPalindromeIgnorePunctuation(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
// skip chars we should ignore
while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
// overskipped -> nothing left to validate
if (i >= j) return true;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindromeIgnorePunctuation(s1);
boolean b2 = validPalindromeIgnorePunctuation(s2);
boolean b3 = validPalindromeIgnorePunctuation(s3);
boolean b4 = validPalindromeIgnorePunctuation(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
최소한 결과는 우리가 예상한 것입니다.
수준은 회문입니까? 팰린드롬이 멋진가요? false 부인은 회문입니까? 사실입니다. 이제 전쟁에서 승리했습니다! 회문? 진실
프로그래밍을 막 시작했다면 문자열 순회 및 비교 알고리즘의 작동 방식을 이해하기 어려울 수 있습니다. 물론 이것을 처리하는 것이 더 좋지만 실제로는 문자열 인 문자 배열을 통해 바로 그 구절의 단순화 된 버전을 작성할 수 있습니다. StringBuffer.reverse 메서드를 사용하여 문자열이 회문인지 확인할 수 있습니다. 영숫자가 아닌 기호와 대문자 및 소문자를 확인하지 않고 가장 간단한 버전을 수행해 봅시다.
public class PalindromeTest5 {
public static boolean validPalindrome(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
String data = buffer.toString();
if (s.equals(data)) {
return true;
}
return false;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
결과는 첫 번째 예와 동일합니다.
수준은 회문입니까? 팰린드롬이 멋진가요? false 부인은 회문입니까? 거짓은 이제 전쟁에서 승리했습니다! 회문? 거짓
원한다면 첫 번째 예에서 했던 것처럼 이 프로그램을 개선할 수 있습니다. 배운 내용을 보강하려면 Java 과정에서 비디오 강의를 시청하는 것이 좋습니다.
GO TO FULL VERSION