알고리즘 전체탐색:: 펠린더룸, 회문 풀이 - 브루스의 회문

안녕하세요. 슝스입니다

오늘은 전체 탐색 두 번째 문제인 (펠린더룸)회문 문제를 포스팅하려고 합니다. 
팰린더룸(회문)은 알고리즘 대회나 회사 코딩 테스트에 많이 나오는 문제로 
알아두면 매우 유익한 알고리즘입니다.

실제로 2017 마이다스아이티 신입 면접 테스트에서 
팰린더룸(회문)이 2번 문제로 출제되었던 적이 있었죠!
(문제를 받아보고 싶으신 분은 아래에 이메일 남겨주시면 보내드리겠습니다.)

혹시 회문이 무엇인지 모르는 분들을 위해 
회문이 무엇인 지 먼저 설명해드릴게요.

 

■회문이란 ?

 

회문이란 '똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장'을 뜻합니다.
이효리는 거꾸로 해도 이효리라는 거 들어보셨죠?
물론 이효리는 거꾸로로 하면 리효이 이기때문에 회문이 아니지만
두음 법칙을 이용해 이효리가 되는 것처럼 말이에요.

쉽게 설명하면 abc 와 같이
앞으로 해도 aba 뒤로해도 aba 와 같은 단어가 회문입니다!

그럼 이제 문제를 한번 살펴볼까요?

 

 

John and Brus are studying string theory at the university.
 Brus like palindromes very much.
 A palindrome is a word that reads the same forward and backward.
 John would like to surpirse Brus by taking a String s, and appending 0
 or more characters to the end of s to obtain a palindrome.
 He wants that palindrome to be as short as possible. Return the
 shortest possible length of a palindrome that John can generate.
 
 존과 브루스는 대학에서 문자열 이론을 공부하고 있습니다. 브루스는 회문을 아주 좋아합니다.
 회문은 앞에부터 읽으나, 뒤에서부터 읽으나 같은 단어를 말합니다. 존은 브루스를 임의의 문자열 s로  회문을 만들어 브루스를 깜짝 놀래켜주고 싶습니다. 이때 존은 문자열 S 뒤에 0개 이상의 숫자를 추가해 회문을 생성하려고 합니다. 존이 생성할 수 있는 가장 짧은 회문의 길이를 리턴하세요.

 함수정의
 public int find(string s)
  
 제약조건
 ▶  영어 소문자('a'~ 'z')로 구성된 1~50글자의 문자열입니다

 

쉽게 보면 이렇게 생각하시면 됩니다.
결국 회문은 양 끝이 같은 문자입니다. 그렇기 때문에 양옆의 수를 먼저 비교하는 것입니다.
만약 a와 b를 비교했을 때처럼 값이 다르다면 
뒤에 똑같은 문자(a)를 붙였다고 생각하고 길이를 늘려 다시 탐색하는 것이죠.
그리고 만약 같다면 그대로 안쪽같이 진행해 나가는 것입니다.

쉽게 생각하면 abab의 회문을 쉽게 만들기 위해서는 
똑같은 문자를 거꾸로 붙인 ababababa 을 만들어주면 되겠죠?
하지만 이것은 최소 회문이 아니기 때문에 길이를 늘려가면서 
회문인지를 전체 탐색해 나가는 것입니다. 

그럼 이제 이 알고리즘을 코드로 짜볼까요?

 

public class PalindromeExam {
  
 public static int find(String s) {  
  for(int i = s.length();;i++) {
   boolean flag = true; 
   for( int j =0; j < s.length(); j++) {
      //반대쪽에 문자가 존재하는 데 다를 경우 플래그를 변경
      if((i - j -1) < s.length() && s.charAt(j) != s.charAt(i-j-1)) {     
            flag = false;
           break;
        }
   }

   if(flag) return i;
  }
 }
  
    public static void main(String[] args) {
  int result = find("abab");
        System.out.println(result);
 }
}

 

 

코드로 짜면 이렇게 됩니다.
for 문 자체에 flag를 두고 true일 경우 i를 반환하게 되어있습니다.
만약 flag가 false로 변경된다면 for 문은 무한 루프를 돌게끔 되어있습니다.
(i가 길이부터 조건 없이 증가하기 때문이죠!)

더 간단하게 보면 회문이라면 flag가 true여서 문자의 길이 i를 반환할 것입니다.
하지만 만약 끝과 끝 숫자가 다르다면 flag를 false로 바꾸고 길이 i를 1 늘리게 됩니다.
이후 전체 탐색을 통해 이를 반복하다 보면 최소의 회문이 나오게 됩니다.

어려우면서 쉬운 회문 좀 이해가 되실지 모르겠습니다.
회문을 푸는 방법은 여러 가지이지만 오늘은 전체 탐색을 통해 풀어보았습니다.
많은 도움이 되셨길 바라면 저는 이만!!