LeetCode 242 Valid Anagram

nayu1105·2023년 8월 31일

leetcode 알고리즘

LeetCode

목록 보기

21/28

LeetCode 242 Valid Anagram 풀러가기

문제

두 문자열이 주어진다.

두 문자열이 애너그램인지 판단하는 함수를 짜면 된다.

애너그램은 각 문자열에서 문자들의 숫자를 바꿨을 때 같으면 애너그램 문자열이다.

예를 들어 "abcde" 와 "edcba"는 애너그램이다.

"bnvm"와 "mbnv" 도 애너그램이다.

문제 분석

첫번째 시도

문자열의 숫자를 담는 count배열을 만들어서 비교했다.

하나의 문자열을 모두 센 후, 다른 문자열에서는 하나씩 감소하며, 0이면 false를 리턴하도록 만들었다.

for 문을 끝까지 완료하면 애너그램을 만들 수 있으니 true를 리턴했다.

코드

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count = new int[26];

        for(int i=0;i<s.length(); i++){
            count[s.charAt(i)-97]++;
        }

        for(int i=0; i<t.length(); i++){
            if(count[t.charAt(i)-97]==0)return false;
            count[t.charAt(i)-97]--;
        }

        return true;
    }
}

결과 : 실패

결과는 실패였다!!

당연히 s.length와 t.length가 같을 줄 알았는데, 문제를 다시 읽으니 그런 조건은 없었다.

이래서 문제를 꼼꼼히 읽어야...

두 문자의 길이가 다를 수 있는 경우도 있다는 것을 깨닫고 코드를 수정했다.

두번째 시도

위의 문제를 해결하기 위해

마지막에 count 배열을 돌면서 0보다 큰 값이 있는지(아직 남은 문자가 있는지) 갯수를 세려다가, 또 for 문을 추가하기는 번거롭다고 생각했다.

그래서 대안으로 처음에 두 길이를 비교해서 같지 않으면 false를 리턴하는 코드를 추가했다.

이로 인해서 탐색 하지 않고, 길이만으로 애너그램 유무를 빠르게 판단할 수 있을 것 같았다.

코드

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count = new int[26];

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

        for(int i=0;i<s.length(); i++){
            count[s.charAt(i)-97]++;
        }

        for(int i=0; i<t.length(); i++){
            if(count[t.charAt(i)-97]==0)return false;
            count[t.charAt(i)-97]--;
        }

        return true;
    }
}

결과 : 성공

Runtime

Memory

성공했다!! 시간이나 메모리도 효율적인 코드 인 것 같다.

다른분의 코드

특이하게 sort를 활용해서 푸신분들도 있었다.

두 문자열을 모두 character 배열로 만들어서 정렬을 한 후, 두 배열이 같은지 비교하는 알고리즘이였다.

애너그럼 문제를 이렇게도 풀 수 있구나 신기했다.

코드

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] arr1 = s.toCharArray();
        char[] arr2 = t.toCharArray();

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        return Arrays.equals(arr1,arr2);
    }
}