[코딩연습] Valid Anagram 유효한 애너그램인지 체크하기

LeetCode 문제 중 난이도 Easy인 Valid Anagram이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

s와 t 두개의 문자열을 받아 t가 s의 애너그램(철자순서를 바꾼말)인지 확인하는 함수를 작성하라.

* 문자열은 소문자로만 이루어져있다고 가정한다.

첫번째 방법은 s와 t를 배열에 담아 정렬한 뒤 비교하는 방법이다. 문자열의 길이가 다르다면 당연히 같을수 없으므로 false를 리턴한다.

class Solution {
    public boolean isAnagram(String s, String t) {
 
        //두 문자열의 길이가 다르면 false
        if (s.length() != t.length()) return false;
        
        //s와 t를 각각 char배열로 변환
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        
        //정렬한다
        Arrays.sort(str1);
        Arrays.sort(str2);
        
        //철자가 같다면 정렬후 두 배열값이 같아야함
        return Arrays.equals(str1, str2);
        
    }
}

16번째줄의 Arrays.equals(array1,array2)는 배열 안의 값이 같은지 확인하는 메소드로 array1.equals(array2)와는 다르다. 후자는 array1==array2와 같은의미로 실제로 두 배열이 주소값까지 같은 동일한 배열인지 확인하는 메소드이다.

두번째 풀이는 각 스펠링이 나온 개수를 배열에 저장하고 비교하는 것이다.

class Solution {
    public boolean isAnagram(String s, String t) {
        
        if (s.length() != t.length()) return false;
        
 
        //a부터 z까지 각각의 알파벳이 나온 횟수를 담기위한 배열 생성
        int[] table = new int[26];
        
        //s의 스펠링들이 각각 몇번 나왔는지 1씩 증가시키면서 table에 저장
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        
        //table에서 t에도 있는애들을 하나씩 감소시킨다
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
}

먼저 a부터 z까지 26개의 알파벳이 나온 횟수를 담기위한 배열을 만든다. 그러고나서 s를 탐색하면서 각 알파벳이 나올때마다 해당 위치의 배열값을 1씩 증가시킨다. 그 다음에 t를 탐색하면서 해당 위치의 배열값을 1씩 감소시킨다. 전체 배열이 0으로 채워지면 true를 리턴한다.

12,17,18번째 줄의 chatAt(i) - 'a'는 알파벳이 아스키코드(0~127)의 값으로 저장되는 것을 이용한 것이다. a~z까지의 알파벳에서 a를 빼주면 0~25까지의 숫자가 나온다.

아스키값 참고

문제 출처 - https://leetcode.com/problems/valid-anagram