[JAVA] Anagram 코딩

총 9개의 문제중 필수로 해야할 6개중 첫 문제이다. 

Two strings are anagrams if one string can be formed by reordering the characters

from the other. Examples of this are:

English: silent / listen German: WIEN / WEIN

rail safety / fairy tales     LAMPE / PALME

a) Implement an efficient method

public static boolean areAnagrams(String s1, String s2)

that checks if the two string s1 and s2 are anagrams. The method should also be

usable for very long strings (e. g. with 1 million characters).You can assume that

only the first 256 characters of the Unicode character set will appear in the strings

(i. e. the characters \u0000 bis \u00FF).

b) Measure the runtime of the method for different lengths n = 100, 1000,

10000,100000, and 1000000. What is the runtime behavior? 

처음으로 나온 과제는 아나그램문제 였다. 

Anagram[아나그램]이란 사전적 정의는 철자순서를 바꾼 말이다.

즉 위에 예시처럼 silent의 철자를 바꿔서 조합하면 listen이 나온다.

해리포터에 나온 Tom Marvolo Riddle 을 바꾸면 I am lord voldmort가 된다.

아나그램 문제는 알고리즘을 하는 사람들이라면 한번쯤은 접해본 문제일 것이다.

먼제 과제는 메인함수와 다른 시간 재는 프로그램을 제시하고 나는 아나그램을 코딩하기만 하면 된다.

내가 생각한 프로그램의 실행 순서는

1. 글자길이를 비교한다.

2. 대소문자를 무시하기위해 모두 소문자로 변형을 시켜준다

3. 문자열을 char[]로 바꾼다.

4. 문자열내 알파벳을 정렬한다

5. char[]형태를 String형태로 바꾼다. 

위 형태로 알고리즘을 구상해보니 

public static boolean areAnagrams(String s1, String s2){

//remove all space

s1 = s1.replaceAll(" ", "");

s2 = s2.replaceAll(" ", "");

  // check lengths of two strings

if ( s1.length() != s2.length() ) {

    return false;

}

// change into small letter and char

char[] character1 = s1.toLowerCase().toCharArray();

char[] character2 = s2.toLowerCase().toCharArray();

// sort

Arrays.sort(character1);

Arrays.sort(character2);

// change char[] to string

String compare1 = new String(character1);

String compare2 = new String(character2);

// Check the string

return compare1.equals(compare2);

}

이런 프로그램이 나왔다.

참고로 이 프로그램에선 교수가 문자 2개를 메인함수에 다 넣어놔서 그 두개가 일치하는지만 보면 되는거였다.