리트코드 - 242. Valid Anagram

 

리트코드 - 242. Valid Anagram

출처 - https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

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

아나그램이란 다른 단어나 구문의 문자를 재배열하여 일반적으로 모든 원래 문자를 정확히 한 번만 사용하여 형성된 단어나 구문을 의미합니다.

 

의사코드

if s와 t의 길이가 다르면     false 리턴 알파벳 갯수만큼 arr 배열 생성 반복문 시작[t 길이만큼 문자열 하나씩 순회]     arr 배열에 문자열을 int로 변환하여 넣음 반복문 종료 반복문 시작[s 길이만큼 문자열 하나씩 순회]     if (arr 배열이 0보다 크지 않으면)         false 리턴     arr 배열에 문자열을 int로 변환하여 넣음 반복문 종료 true 리턴

 

풀이코드

방법1(배열 사용)

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] arr = new int[26];

        for (char data : t.toCharArray()) {
            arr[data - 'a']++;
        }

        for (char data2 : s.toCharArray()) {
            if (!(arr[data2 - 'a'] > 0)) {
                return false;
            }

            arr[data2 - 'a']--;
        }
        return true;
    }
}

방법2 (Map 사용)

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
           return false;
        }
        Map<Character, Integer> map = new HashMap<>();

        for (char data : t.toCharArray()) {
            map.put(data, map.getOrDefault(data, 0) + 1);
        }
        for (char data2 : s.toCharArray()) {
            if (map.get(data2) == null) {
                return false;
            }

            map.put(data2, map.get(data2) - 1);
        }

        for (int value : map.values()) {
            if (value != 0) {
                return false;
            }
        }

        return true;
    }
}
}

코드설명

우선 s의 길이와 t의 길이가 다르면 값을 비교할 이유가 없으므로 false를 리턴한다.

 

그리고 기본적인 원리는 방법 1과 2가 같은데 알파벳을 넣을 빈 배열(Map)로 만들고,t 문자열을 순회하면서 배열(Map)에 값을 1씩 추가한다.

 

방법 1에서는 arr[data - 'a'] 방식을 사용했는데, char 'a'는 int로 97이다.(아스키코드)

따라서'a'-'a' 하면 1번째 배열에 값을 넣을 수 있고, 'z'-a'하면 마지막인 26번째 배열에 값을 넣을 수 있다.

이렇게 해서 다시 이 배열(Map)과 s 문자열을 순회하면서 arr 배열의 값이 0보다 크지 않으면 false를 리턴하고, 크다면 배열값을 -1 해준다.

 

s를 끝까지 잘 순회할 수 있으면 true를 리턴한다.

 

방법 2에서는 Map을 만들고 key=알파벳 으로하여 value에 값이 있으면 기존값+1, 없으면 0+1을 해준다.

이렇게 만들어진 Map을 s문자열을 순회하면서 map에 key값에 넣고 null이면 false를 리턴 아니면 value를 1 빼준다.

반복을 마치고 map에서 value=0 인 값이 있다면 false를 리턴하고, 모두 통과하면 true를 리턴한다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

둘의 시간복잡도와 공간복잡도는 빅O표기로는 같지만 실제로는 배열을 사용한 것이 조금 더 빠르다.(5ms < 14ms)

 

문제를 풀며 생각한 흐름과 배운 점

처음에 일반 배열의 방법대로 해결하고 Arrays.sort로 푸는건 어떨까 궁금해서 다시 풀어봤다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        String[] arr = s.split("");
        String[] arr2 = t.split("");

        Arrays.sort(arr);
        Arrays.sort(arr2);

        if (arr.length != arr2.length) {
            return false;
        }

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

하지만 런타임 64ms(5.5%), 메모리 53mb(6.67%)효율이 너무 좋지 못했다.

처음 배열은 푼 방법은 런타임 2ms(99.21%)에 메모리 43.8mb(22.71%) 으로 런타임은 괜찮고 메모리가 많이 차지하는 문제였다.

메모리를 어떻게 줄일까 고민했다.

 

리팩토링

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] arr = new int[26];

        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
            arr[t.charAt(i) - 'a']--;
        }

        for (int count : arr) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

위에서 s랑 t의 길이가 다르면 false를 리턴하기때문에 두 개의 길이가 같다는 전제하에 시작하므로 같이 처리하기로 했다.

알파벳 갯수 배열에 각각 알파벳을 더하거나 빼고, 최종 arr 배열에 count가 0이 아닌 값이 있으면 false를 리턴한다.

이렇게 하니 런타임은 5ms(55.74%), 메모리는 42mb(85.6%)가 나왔다.

 

메모리는 줄었지만 런타임이 조금 늘었다.

투 포인터로 리팩토링 했지만 결과는 비슷했다.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] arr = new int[26];
        int left = 0;
        int right = s.length() - 1;

        while (left <= right) {
            if (left == right) {
                arr[s.charAt(left) - 'a']++;
                arr[t.charAt(left) - 'a']--;
            } else {
                arr[s.charAt(left) - 'a']++;
                arr[s.charAt(right) - 'a']++;
                arr[t.charAt(left) - 'a']--;
                arr[t.charAt(right) - 'a']--;
            }

            left++;
            right--;
        }

        left = 0;
        right = arr.length - 1;

        while (left <= right) {
            if (arr[left] != 0 || arr[right] != 0) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

어떻게든 줄여보고자 투포인터를 두 번 써봤는데 런타임도 메모리도 줄은 부분이 없었다..

 

기타

만약 알파벳이 아니라 한글이나 특수문자까지 비교한다면 일반 배열을 쓰는 것보다 map을 쓰는것이 합리적일 것이다.

코테 문제를 풀 때 시간복잡도와 공간복잡도 제한이 있다면 보통은 공간복잡도는 고려하지 않고, 시간복잡도만 고려해야 한다고 하는데...(시간초과가 나기 때문)

공간을 초과하지 않는 범위 내에서 시간 복잡도가 빠른 코드를 떠올리는 연습을 해야겠다.

 

다른 코드들도 봤는데 특별히 런타임과 메모리를 줄인 부분이 없어보여서 이번 포스팅은 생략한다.

 

정리

문자열 문제를 풀 때는 시간 복잡도를 먼저 고려하며 이후 공간 복잡도도 고려하자.