[Array & Hash] Valid Anagram

문제

두 개의 문자열 s와 t가 주어졌을 때, t가 s의 아나그램인 경우 true를 반환하고, 그렇지 않은 경우 false를 반환합니다.

아나그램이란, 다른 단어나 문장의 글자를 재배열하여 만든 단어나 문장을 의미하며, 보통 원래 단어나 문장의 모든 글자를 정확히 한 번씩만 사용합니다.

---

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false

---

나의 풀이

class Solution {
    public boolean isAnagram(String s, String t) {
    
    	// 1. 문자열을 배열로 만들어 오름차순으로 정렬한다
        char[] characters = s.toCharArray();
            Arrays.sort(characters);

        char[] characters2 = t.toCharArray();
            Arrays.sort(characters2);

			// 2. 정렬한 배열의 내용이 동일한지 비교
            if (characters==characters2) {
                return true;
            } return false;
    }
}

결과

---

오답 노트

• 배열 비교 시 == 연산자는 배열 참조 자체를 비교하는 것, 배열 내용 비교를 정확히 할 수 없음
• 배열 내용 비교 시 Arrays.equals() 사용

public boolean isAnagram(String s, String t) {
        char[] characters = s.toCharArray();
            Arrays.sort(characters);

        char[] characters2 = t.toCharArray();
            Arrays.sort(characters2);

            return Arrays.equals(characters, characters2);
    }

• 정렬 알고리즘 : O(N log N)의 시간 복잡도

---

다른 풀이

class Solution {

    public boolean isAnagram(String s, String t) {
        // 두 문자열의 길이가 다르면, 아나그램이 될 수 없으므로 바로 false 반환
        if (s.length() != t.length()) {
            return false;
        }

        // 알파벳의 개수만큼의 크기를 가진 배열을 사용하여 각 문자의 발생 횟수를 카운트
        int[] count = new int[26];

        // 첫 번째 문자열의 각 문자에 대해 카운트 증가
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }

        // 두 번째 문자열의 각 문자에 대해 카운트 감소
        for (int i = 0; i < t.length(); i++) {
            count[t.charAt(i) - 'a']--;

            // 만약 어떤 문자의 카운트가 음수가 되면, 아나그램이 아님
            if (count[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        // 모든 문자에 대해 카운트가 0이면 아나그램임
        return true;
    }
}

• 아스키코드 a(97) - z(122)
• 'a' 를 빼면 a 는 0, b 는 1 ....
• count 배열 [0,0,0,0,0,0.....,0] 에서 알파벳에 해당하는 인덱스를 카운트
• 각 문자열을 한 번씩만 순회하기 때문에, O(N) 시간 복잡도