Valid Anagram

문제

두 개의 문자열 s와 t가 주어질 때, t가 s의 애너그램(Anagram)인지 판별하는 프로그램을 작성하는 문제입니다. 애너그램이란 단어나 문장의 철자 순서를 바꾸어 다른 단어나 문장으로 만드는 것을 말합니다. 즉, 두 문자열이 구성하는 알파벳의 종류와 개수가 완벽하게 동일해야 합니다.

• 입력: 알파벳 소문자로만 이루어진 문자열 s와 t (1 <= s.length, t.length <= 5 * 10^4)
• 출력: t가 s의 애너그램이면 true, 아니면 false 반환

링크: https://leetcode.com/problems/valid-anagram

풀이: 알파벳 카운팅 배열을 활용한 O(N) 최적화 탐색

두 문자열을 정렬한 뒤 비교하는 방식(시간 복잡도 O(N log N)) 대신, 알파벳의 개수가 26개로 고정되어 있다는 점을 활용하여 길이가 26인 정수 배열을 사용하는 방식(시간 복잡도 O(N))으로 성능을 극대화했습니다.

• 조기 종료 (길이 비교): 두 문자열의 길이가 다르다면 애너그램이 될 수 없으므로 탐색을 시작하기 전에 즉시 false를 반환합니다.
• 카운팅 배열 선언: 알파벳 소문자 'a'부터 'z'까지의 빈도수를 기록할 크기 26의 정수 배열 cnt를 선언합니다.
• 단일 반복문을 통한 빈도수 증감:
  • 두 문자열의 길이가 같으므로 하나의 for문 안에서 s와 t의 문자를 동시에 확인합니다.
  • s에 포함된 문자는 배열의 해당 인덱스 값을 1 증가시킵니다. (cnt[s.charAt(i) - 'a']++)
  • t에 포함된 문자는 배열의 해당 인덱스 값을 1 감소시킵니다. (cnt[t.charAt(i) - 'a']--)
• 최종 검증: 애너그램이라면 증가한 만큼 정확히 감소했어야 하므로, 모든 연산이 끝난 후 cnt 배열의 모든 원소는 0이어야 합니다. 배열을 순회하며 0이 아닌 값이 하나라도 있다면 false를, 무사히 통과하면 true를 반환합니다.

코드

class Solution {
    public boolean isAnagram(String s, String t) {
        // 1. 길이가 다르면 애너그램 불가
        if (s.length() != t.length()) {
            return false;
        }

        // 2. 알파벳 빈도수를 저장할 배열 (소문자 26개)
        int[] cnt = new int[26];

        // 3. 한 번의 순회로 s는 더하고, t는 뺌
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
            cnt[t.charAt(i) - 'a']--;
        }

        // 4. 모든 알파벳의 빈도수 합산이 0인지 확인
        for (int i = 0; i < 26; i++) {
            if (cnt[i] != 0) {
                return false;
            }
        }

        return true;
    }
}

알고리즘 분류

문자열 (String), 해시 테이블 (Hash Table), 카운팅 배열 (Counting Array)