Anagram 문제풀기

 

Anagram이란?

https://m.blog.naver.com/PostView.nhn?blogId=r_mento&logNo=90174514542&proxyReferer=https:%2F%2Fwww.google.com%2F

글자 순서의 비밀! 아나그램(Anagram)이란?

 

 

Two strings,  and , are called anagrams if they contain all the same characters in the same frequencies. For example, the anagrams of CAT are CAT, ACT, TAC, TCA, ATC, and CTA.

Complete the function in the editor. If  and  are case-insensitive anagrams, print "Anagrams"; otherwise, print "Not Anagrams" instead.

Input Format

The first line contains a string denoting .
The second line contains a string denoting .

Constraints

• 1 <= length(a), length(b) <=50
• Strings  and  consist of English alphabetic characters.
• The comparison should NOT be case sensitive.

Output Format

Print "Anagrams" if  and  are case-insensitive anagrams of each other; otherwise, print "Not Anagrams" instead.

Sample Input 0

anagram margana

Sample Output 0

Anagrams

Explanation 0

CharacterFrequency: anagramFrequency: margana

A or a	3	3
G or g	1	1
N or n	1	1
M or m	1	1
R or r	1	1

 

 

처음 이 문제를 접근할때 평소에 정말 편리하게 사용한 Arrays.sort()를 사용못하는 제약사항이 있다.

또한 퀵소트를 만든다고하면 이 문제를 해결하면 배보다 배꼽이 더 큰 짓일 수 도 있어서 생각보다 시간소모를 했다

 

 

내가 풀이한 방식

        char[] arr = a.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                .toString().toCharArray();
        char[] arr2 = b.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                .toString().toCharArray();

        int count = 0;
        for(int i = 0; i < arr.length; i++) {
                if(arr[i] == arr2[i]) count++;
        }
        return count == arr.length;

 

확실히 내가 짠코드는 char[]에 문자 array들이 보기 안좋게 저장되는 방식이다. 더 많은 생각을 가진건 아래에 서술했다.

 

 

 

Discussions에 한 인도인이 푼 코드이다.

if(a.length() != b.length()) return false;
        int c[] = new int[26], d[] = new int[26] ;
        a = a.toUpperCase();
        b = b.toUpperCase();
        for(int i=0; i<a.length(); i++){
            c[a.charAt(i) - 'A']++;
            d[b.charAt(i) - 'A']++;
        }
        for(int i =0;i<26; i++)
            if(c[i] != d[i] ) return false;
        return true;

 

난 첫번째 가장 기본적인 제약사항에 메모리 크기 할당을 안지켰다. 또한 불필요하게 O(N)의 시간복잡도를 가진 후, 최종 카운트를 세고 검증하는게 불필요한 짓거리였다

 

추가로 생각해야할점이 메모리 할당 사이즈가 50이하로 제약이 걸려있고, 인덱스가 0부터 25까지 총 26개 알파벳의 공간복잡도를 가지게되므로 결국엔 두배열을 합친 크기가 두알파벳을 합친것과 동일하다.