160718.md

Daily Algorithms learning

* 기본 알아둘 것 정리 링크

1. Anagram

• 문제
• Anagram은 어떤 단어나 문장의 글자의 순서를 바꾸어 다른 단어나 문장을 만드는 개념이다.
• 어떠한 단어 2개를 입력 받고 이 두 글자가 아나그램인지 증명 해 보자.
• 구현

public class AnagramMain {
  public static void main(String[] args) {
    // true case
    System.out.println("[1] Anagram Test 1 : " + (isAnagramString_CaseOne("asdf", "sfad")));
    System.out.println("[1] Anagram Test 2 : " + (isAnagramString_CaseOne("Anagram", "namAarg")));
    System.out.println("[1] Anagram Test 3 : " + (isAnagramString_CaseOne("kangSungWoo", "oowgungSkan")));

    // false case
    System.out.println("[1] Anagram Test 4 : " + (isAnagramString_CaseOne("gramAna", "AnagramA")));
    System.out.println("[1] Anagram Test 5 : " + (isAnagramString_CaseOne("Anagram", "AAAgram")));
    System.out.println("[1] Anagram Test 6 : " + (isAnagramString_CaseOne("KangSungWoo", "JNgoOWZungK")));
    
    System.out.println("= = = = = = = = = = = = = = = = = = = = = = ");
    
    // true case
    System.out.println("[2] Anagram Test 1 : " + (isAnagramString_CaseTwo("asdf", "sfad")));
    System.out.println("[2] Anagram Test 2 : " + (isAnagramString_CaseTwo("Anagram", "namAarg")));
    System.out.println("[2] Anagram Test 3 : " + (isAnagramString_CaseTwo("kangSungWoo", "oowgungSkan")));

    // false case
    System.out.println("[2] Anagram Test 4 : " + (isAnagramString_CaseTwo("gramAna", "AnagramA")));
    System.out.println("[2] Anagram Test 5 : " + (isAnagramString_CaseTwo("Anagram", "AAAgram")));
    System.out.println("[2] Anagram Test 6 : " + (isAnagramString_CaseTwo("KangSungWoo", "JNgoOWZungK")));
  }

  /**
   * 공간을 26*2만큼 더 쓰지만 시간은 O[N]인 아나그램 체크 메소드.
   */
  public static boolean isAnagramString_CaseOne(String str1, String str2) {
    char[] char1 = str1.toLowerCase().toCharArray();
    char[] char2 = str2.toLowerCase().toCharArray();

    if (char1.length != char2.length) {
      return false;
    }

    int[] counts = new int[26];
    Arrays.fill(counts, 0);

    for (int i = 0; i < char1.length; i++) {
      // 찾은 문자에서 'a'를 빼서 0번째 인덱스 부터 26까지 할당 시킨다.
      counts[char1[i] - 'a']++; // 1번 배열에서 찾은 문자에 counts배열 index의 값을 증가 시켜 준다.
      counts[char2[i] - 'a']--; // 2번 배열에서 찾은 문자에 counts배열 index의 값을 감소 시켜 준다.
    }

    // 만약 두 문자열이 아나그램이 맞다면, counts배열은 모두 0으로 세팅 되어 있을 것 이다.
    for (int i = 0; i < counts.length; i++) {
      if (counts[i] != 0) {
        return false;
      }
    }
    return true;
  }

  /**
   * 공간은 O[N]만큼만 쓰지만 시간은 최소 O[N log N]이상인 아나그램 체크 메소드.
   */
  public static boolean isAnagramString_CaseTwo(String str1, String str2) {
    char[] char1 = str1.toLowerCase().toCharArray();
    char[] char2 = str2.toLowerCase().toCharArray();

    if (char1.length != char2.length) {
      return false;
    }

    // 문자열 1과 2를 정렬 했을때 두개의 정렬 값이 같다면 아나그램이다.
    Arrays.sort(char1);
    Arrays.sort(char2);
    
    for (int i = 0; i < char1.length; i++) {
      if(char1[i] != char2[i]) {
        return false;
      }
    }
    return true;
  }
}

1. Pelindrome

• 문제
• Pelindrome은 어떤 단어나 문장을 앞에서 읽으나 뒤에서부터 읽으나 같은 뜻을 가진 문장을 말한다.
• 예를 들면 tomato, race car, madam등이 있다.
• 이러한 펠린드롬을 구현해 보자.
• 구현

public class PelindromeMain {
  public static void main(String[] args) {
    // true case
    System.out.println("[1] Pelindrome Test Case 1 : " + isPalindromeString("rotator"));
    System.out.println("[1] Pelindrome Test Case 2 : " + isPalindromeString("madam"));
    System.out.println("[1] Pelindrome Test Case 3 : " + isPalindromeString("race car"));
    
    // false case
    System.out.println("[1] Pelindrome Test Case 4 : " + isPalindromeString("release"));
    System.out.println("[1] Pelindrome Test Case 5 : " + isPalindromeString("release"));
    System.out.println("[1] Pelindrome Test Case 6 : " + isPalindromeString("release"));
  }

  /**
   * 입력한 문자열 배열의 왼쪽 끝(0 ~ length/2)으로부터
   * 오른쪽 끝(length - 1 - i)과의 문자를 서로 비교 한다. 
   */
  public static boolean isPalindromeString(String str) {
    char[] chrs = str.toLowerCase().replaceAll(" ", "").toCharArray();

    for (int i = 0; i < chrs.length / 2; i++) {
      if (chrs[i] != chrs[chrs.length - 1 - i]) {
        return false;
      }
    }
    return true;
  }
}