[LeetCode] 242. Valid Anagram

두 문자열 s와 t가 주어지면 t가 s의 애너그램이면 참을 반환하고, 그렇지 않으면 거짓을 반환합니다.

애너그램은 다른 단어 또는 구의 글자를 재배열하여 만든 단어 또는 구문으로, 일반적으로 원래 글자를 모두 정확히 한 번 사용합니다.

 

Example 1:

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

Example 2:

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

 

문제접근

해시맵을 이용해 접근하였습니다.

 

중요한것은 s와 t의 길이가 같지않으면 false라는 것입니다.

나머지는 map을 이해하고있다면 크게 어렵지 않습니다.

 

public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) {
            return false;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        int cnt = 0;

        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        for (int i = 0; i < t.length(); i++) {
            char key = t.charAt(i);
            if (map.containsKey(key) && map.get(key) > 0) {
                cnt++;
                map.put(key, map.get(key) - 1);
            }
        }

        System.out.println("s.length() <= cnt : " + s.length() + " " + cnt);
        return s.length() == cnt;
    }

 

시간복잡도

해시맵을 사용하고 있고, for-loop를 한번 돌고있습니다.

O(n)의 시간복잡도를 갖고있습니다.

 

다른사람의 풀이

sort를 이요해 정렬하고, equals메서드를 사용해서 간단하게 풀이한 코드입니다.

 

  public boolean isAnagram(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        
        return Arrays.equals(sChars, tChars);
    }

 

시간복잡도

Arrays의 sort는 DualPivotQuicksort를 사용하고있습니다.

O(n log(n))의 시간복잡도를 소요합니다. 

그리고 Arrays.equals는 O(n)의 시간복잡도를 소요합니다.

 

따라서 위 로직의 시간복잡도는 O(n log(n))입니다.

 

느낀점

문제를 어떻게 접근하냐에 따라 문제풀이법이 달라지고

코드의 가독성이 달라진다는것을 알았습니다.

 

효율적인 코드와 가독성있는 코드를 작성하기위해 노력하겠습니다.

 

참고

✅3 Method's 🤯 || C++ || JAVA || PYTHON || Beginner Friendly🔥🔥🔥 - Valid Anagram - LeetCode