[ LeetCode | Java ] 242. Valid Anagram

dokim·2023년 8월 30일

[LeetCode] Top 150 leetcode

[LeetCode] Top Interview 150

목록 보기

22/51

🏷️242. Valid Anagram

1. 문제 설명

두 개의 문자열 s와 t가 주어지면, t가 s의 애너그램이면 true를 반환하고 그렇지 않으면 false를 반환합니다.
애너그램은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어나 구문의 문자를 재배열하여 형성된 단어나 구문입니다.

2. 접근 방법

문자열 s와 t에서 대칭되는 똑같은 무자를 찾아야하는데 이중 반복문으로 완전탐색하여 결과값을 찾기에는 비효율적이라 생각하여 HashMqp 을 사용하여 문제를 해결하였습니다.
반복문을 통해 s의 문자열에서 가각의 문자를 HashMap의 Key값으로 저장하며 value는 해당 문자의 빈출 수를 저장하였습니다.
문자열 t의 각각의 문자를 반복문으로 조회하여 저장된 HashMap에서 Key값과 비교하고 value를 체크합니다.
HashMap에 저장된 Key에 t의 문자가 있고 해당 Key의 Value가 0 이상이면 Value-1을 하여 데이터를 수정합니다.
만약 위의 조건이 만족하지 않으면 't'의 문자가 없거나, 문자 개수가 다르다는 의미이므로 false를 반환합니다.
그리고 반복문이 끝나고 s와 t의 문자열 길이를 확인하여 조건처리를 해줍니다.

3. 구현 코드

class Solution {
    public boolean isAnagram(String s, String t) {
       
        Map<Character, Integer> map = new HashMap<Character, Integer>();
         
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        for(int i = 0; i < t.length(); i++){
            if( map.containsKey(t.charAt(i))){
                if (map.get(t.charAt(i)) > 0)
                    map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
                else
                    return false;
            }
            else
                return false;
        }
        
        return  s.length() ==  t.length() ? true : false;
        
    }
}

시간 복잡도 : O(n)
공간 복잡도 : O(1)
- 최악의 경우 HashMap의 공간 복잡도는 O(n)이지만 여기는 문자열에 있는 알파벳만 사용하며 그 개수가 제한되어 있습니다.
  그래서 O(1)의 공간 복잡도를 가진다고 볼 수 있을 것 같습니다.

4. 개선 사항

1) 중복 코드 제거

이중 if문으로 조전처리를 하여 else문에서 이중으로 똑같이 return false;을 반환하는 중복된 코드가 있어 수정하였습니다.

이전 코드와 기교하면 기능적으로 달라진 점은 없습니다. 다만, 가독성이 조금 더 좋아졌습니다..

class Solution {
    public boolean isAnagram(String s, String t) {
        
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        for(int i = 0; i < s.length(); i++)
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        
        for(int i = 0; i < t.length(); i++){
            if( map.containsKey(t.charAt(i)) && map.get(t.charAt(i) ) > 0)
                    map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
            else
                return false;
        }
        
        return  s.length() ==  t.length() ? true : false;
    }
}

2) Array로 해결

문자열 s와 t를 문자 배열로 만들어 정렬을 하고 비교하여 간단하게 문제를 해결할 수 있습니다.

문제를 해결하고 다른 분들의 코드를 보다가 배열을 너무나 잘 사용하여 가지고 왔습니다.
다음에는 이런 방식으로 해결할 수 있는 문제를 만나서 사용해보고 싶습니다. 😊


class Solution {
    public boolean isAnagram(String s, String t) {
        
        char[] sToChar = s.toCharArray();
        char[] tToChar = t.toCharArray();
        
        Arrays.sort(sToChar);
        Arrays.sort(tToChar);
        
        return  Arrays.equals(sToChar, tToChar);
    }
}

5. 최종 회고

어떻게 더 간결하고 효율적인 코드를 만들 수 있까 고민을 하면서 풀었습니다. 여러 시도를 하며 코드를 완성하고 테스터를 돌리며 완성도를 높여가며 통과를 했습니다. 처음에는 만족스러운 코드였지만 다른 분들의 코드를 보니 아직 배울 것이 많습니다.
이번 문제를 통해 HashMap의 사용법에 대해 더 알아보고 활용해 보고 Array의 활용에 대해 다시 생각하게 되었습니다. 한 문제로 여러 지식과 경험을 가지고 갈 수 있어서 만족스러운 문제였습니다.😀