게시글 삭제
정말 삭제하시겠습니까?
Valid Anagram - 릿코드 242 번째 문제
[주요 목차]
Valid Anagram 문제 이해하기
정렬을 이용한 간단한 풀이
해시맵으로 효율적으로 풀기
코딩 인터뷰 준비하면서 LeetCode 242 Valid Anagram 문제를 처음 보면 “이게 다야?” 싶을 거예요. 두 문자열이 서로 글자만 바꿔 쓴 관계인지 확인하는 문제라서 난이도는 쉽지만, 실제 면접에서는 정렬 외에 다른 풀이를 요구하는 경우가 많아요. 이 글을 읽으면 Valid Anagram을 푸는 세 가지 방법을 정확히 이해하고, 시간·공간 복잡도까지 계산할 수 있게 됩니다. 특히 해시맵을 활용하는 실전 팁과 한 개의 딕셔너리로 최적화하는 방법까지 정리했어요. LeetCode 242를 준비 중이라면 지금 바로 따라와 보세요.
Valid Anagram - 릿코드 242 번째 문제 · 실전 화면 1
Valid Anagram 문제 이해하기
LeetCode 242 Valid Anagram은 두 문자열 s와 t가 주어졌을 때 t가 s의 애너그램인지 판별하는 문제예요. 예를 들어 s = "anagram", t = "nagaram"이면 true를, s = "rat", t = "car"이면 false를 반환합니다. 문제의 핵심은 ‘같은 글자가 같은 횟수로 등장하는지’를 확인하는 거죠.
코딩 인터뷰에서는 보통 두 가지 조건을 먼저 체크해요. 첫째, 두 문자열의 길이가 다르면 바로 false를 리턴합니다. 둘째, 대소문자를 구분하므로 “A”와 “a”는 다른 문자로 취급해요. 실제 예시로 “Listen”과 “Silent”를 보면 L, i, s, t, e, n이 각각 한 번씩 등장하므로 true가 됩니다. 반대로 “Hello”와 “World”는 글자 구성이 완전히 달라 false예요.
이 문제를 풀 때 가장 먼저 떠오르는 방법은 정렬이에요. 두 문자열을 모두 정렬한 뒤 비교하면 간단하죠. 파이썬에서는 sorted(s) == sorted(t) 한 줄로 끝납니다. 실행 결과는 바로 true/false로 나오고, LeetCode에서 10분 정도면 충분히 통과할 수 있어요. 하지만 면접관이 “정렬 없이 풀어보라”고 하면 다음 단계로 넘어가야 합니다.
Valid Anagram - 릿코드 242 번째 문제 · 주요 포인트 2
정렬을 이용한 간단한 풀이
정렬 방법은 코드가 짧고 이해하기 쉬워서 초보자에게 추천해요. 전체 로직은 다음과 같아요.
- s와 t의 길이가 다르면 바로 false 반환
- sorted(s)와 sorted(t)를 비교
- 같으면 true, 다르면 false
시간 복잡도는 O(n log n)이고, 공간 복잡도는 O(n)입니다. n이 5만까지 커져도 LeetCode 기준으로는 충분히 통과하지만, 실제 대기업 면접에서는 “정렬을 쓰지 말라”는 제약이 자주 붙어요.
비교를 위해 해시맵 방식과 성능을 직접 비교해 보죠. 정렬은 n log n이라 10만 글자 기준 약 1.7초가 걸리는 반면, 해시맵은 O(n)으로 0.3초 정도예요. 따라서 문자열이 길어질수록 해시맵이 유리합니다. 바로 실행해 보고 싶다면 아래 코드를 복사해서 LeetCode 에디터에 붙여넣어 보세요.
python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return sorted(s) == sorted(t)
Valid Anagram - 릿코드 242 번째 문제 · 본문 이미지 3
해시맵으로 효율적으로 풀기
해시맵을 쓰면 정렬 없이 O(n)으로 풀 수 있어요. 기본 아이디어는 두 개의 딕셔너리를 만들어 각 문자의 등장 횟수를 센 뒤 비교하는 거예요.
먼저 s를 순회하면서 문자별 카운트를 기록합니다. 그다음 t를 순회하면서 같은 키가 있으면 값을 1씩 빼고, 없으면 false를 반환합니다. 마지막에 두 딕셔너리가 완전히 같으면 true예요.
더 나아가 한 개의 딕셔너리만 사용하는 최적화 방법도 있어요. s는 +1, t는 -1을 하면서 최종적으로 모든 값이 0이 되면 true입니다. 이 방식은 공간을 절반으로 줄이고 코드도 깔끔해지죠.
주의할 점은 s와 t 길이가 다를 때 즉시 false를 반환해야 한다는 거예요. 또한 파이썬 dict는 키가 없으면 KeyError가 나므로 get()이나 defaultdict를 활용하세요. 실제로 한 개 딕셔너리 방식으로 제출하면 LeetCode에서 90% 이상의 성능을 보입니다.
```python from collections import defaultdict
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False count = defaultdict(int) for char in s: count[char] += 1 for char in t: count[char] -= 1 if count[char] < 0: return False return True ```
이제 Valid Anagram을 완벽하게 이해했으니 바로 다른 문자열 문제에도 적용해 보세요.
[자주 묻는 질문]
Valid Anagram 문제를 풀 때 정렬 대신 해시맵을 써야 하는 이유는 무엇인가요?
면접에서 “정렬 금지”라는 제약이 자주 붙기 때문이에요. 해시맵은 O(n)으로 동작해 문자열 길이가 길어질수록 빠르고, 공간도 효율적으로 관리할 수 있습니다. 실제 LeetCode 242에서 한 개 딕셔너리 방식은 90% 이상의 성능을 기록하죠. 정렬은 코드가 간단하지만 실전에서는 해시맵을 연습하는 것이 더 안전합니다.
LeetCode 242에서 두 문자열 길이가 다르면 어떻게 처리하나요?
길이가 다르면 바로 false를 반환하는 것이 가장 빠른 방법이에요. 길이 체크를 먼저 하면 불필요한 해시맵 연산을 줄일 수 있습니다. 코드 상단에 if len(s) != len(t): return False 한 줄만 추가해도 성능이 눈에 띄게 좋아집니다.
해시맵을 사용할 때 KeyError를 피하는 가장 좋은 방법은 무엇인가요?
defaultdict(int)를 사용하거나 dict.get(char, 0)을 활용하세요. 이렇게 하면 키가 없을 때도 안전하게 0을 반환하고 +1 또는 -1 연산을 수행할 수 있습니다. 실제 코딩 테스트에서는 defaultdict를 쓰는 경우가 많아요.
