LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Valid Anagram" 문제입니다.
--> https://leetcode.com/problems/valid-anagram/description/
문제 :
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1 :
Input : s = "anagram", t = "nagaram"
Output : true
Example 2 :
Input : s = "rat", t = "car"
Output : false
Constraints :
- 1 <= s.length, t.length <= 5 * 10^4
- s and t consist of lowercase English letters.
Follow up :
What if the inputs contain Unicode characters?
How would you adapt your solution to such a case?
이 문제는 두 문자열 s와 t가 주어질 때, t가 s의 애너그램(Anagram)인지 확인하는 문제입니다. 애너그램은 다른 단어나 구문의 문자를 다시 배열하여 형성된 단어나 구문을 의미하며, 원래의 모든 문자를 정확히 한 번 사용해야 합니다.
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> charCountS = new HashMap<>();
Map<Character, Integer> charCountT = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
charCountS.put(c, charCountS.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
charCountT.put(c, charCountT.getOrDefault(c, 0) + 1);
}
return charCountS.equals(charCountT);
}
}
이 코드는 두 문자열 s와 t가 애너그램인지 확인하기 위해 두 개의 해시맵을 사용하여 각 문자열의 문자 빈도를 추적합니다. 각 문자열의 빈도 해시맵을 비교하여 두 문자열이 애너그램인지 확인합니다.
- 문자열 길이 비교 :
- 두 문자열 s와 t의 길이가 다르면 애너그램이 될 수 없으므로 바로 false를 반환합니다.
- 문자 빈도 계산 :
- 두 개의 해시맵 charCountS와 charCountT를 사용하여 각각의 문자열에 대한 문자 빈도를 계산합니다.
- 첫 번째 문자열 s에 대해 각 문자의 빈도를 계산하고 해시맵 charCountS에 저장합니다.
- 두 번째 문자열 t에 대해 각 문자의 빈도를 계산하고 해시맵 charCountT에 저장합니다.
- 빈도 비교 :
- 두 해시맵 charCountS와 charCountT가 같은지를 비교합니다. 만약 두 해시맵이 동일하다면, 두 문자열은 애너그램입니다. 그렇지 않으면 애너그램이 아닙니다.
시간 복잡도 :
- O(n) : 여기서 n은 문자열의 길이입니다.
- 문자열 s와 t를 각각 한 번씩 순회하면서 각 문자의 빈도를 계산하므로, O(n) 시간이 소요됩니다.
- 해시맵의 put 연산은 평균적으로 O(1)이므로, 전체 시간 복잡도는 O(n)입니다.
공간 복잡도
- O(1) 또는 O(m) : 여기서 m은 사용된 고유 문자의 수입니다.
- 영어 소문자만 사용된다면 공간 복잡도는 O(1)입니다. (고정된 26개의 문자를 사용하므로)
- 일반적으로 문자의 종류가 많아질수록 해시맵 크기가 커질 수 있지만, 해시맵은 각 문자열의 문자 빈도를 저장하므로 최대 m개의 키-값 쌍을 가질 수 있습니다.
코드의 장단점
장점
- 유연성 : 유니코드 문자나 다양한 문자셋을 지원하기 위해 해시맵을 사용할 수 있습니다.
- 직관성 : 두 해시맵을 사용하여 문자열의 빈도를 비교하는 방식은 직관적이며 이해하기 쉽습니다.
단점
- 공간 사용 : 두 개의 해시맵을 사용하므로 공간 사용이 두 배가 됩니다. 하지만 각 문자열에 대해 별도의 빈도 맵을 유지하기 때문에 두 문자열이 매우 클 경우 공간 사용이 증가할 수 있습니다.
그래서 개선한 코드가 이겁니다 :
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] charCount = new int[26]; // 소문자 영어 알파벳에 대한 카운트 배열
// 문자열 s의 각 문자에 대해 카운트를 증가
for (char c : s.toCharArray()) {
charCount[c - 'a']++;
}
// 문자열 t의 각 문자에 대해 카운트를 감소
for (char c : t.toCharArray()) {
charCount[c - 'a']--;
}
// 모든 카운트가 0인지 확인
for (int count : charCount) {
if (count != 0) {
return false; // 0이 아니면 애너그램이 아님
}
}
return true; // 모든 카운트가 0이면 애너그램임
}
}
이 코드는 두 문자열 s와 t가 애너그램인지 확인하는 효율적인 방법을 제공합니다. 이 방법은 각 문자열의 문자의 빈도를 비교하여 두 문자열이 같은 문자를 같은 빈도로 포함하고 있는지를 검사합니다. 이 방법은 정렬을 사용하는 방법보다 더 효율적이며, O(n) 시간 복잡도를 가집니다.
- 길이 비교 :
- 두 문자열의 길이가 다르면 애너그램이 될 수 없으므로 즉시 false를 반환합니다.
- 문자 빈도 카운트 배열 초기화 :
- 길이가 26인 정수 배열 charCount를 생성하여 각 문자의 빈도를 저장합니다.
- 이 배열의 인덱스는 문자 'a'부터 'z'까지의 알파벳 순서와 대응됩니다.
- 문자 빈도 증가 :
- 문자열 s의 각 문자에 대해 해당 문자의 빈도를 증가시킵니다.
- c - 'a'를 사용하여 문자 c의 인덱스를 계산합니다. 예를 들어, 'a'는 인덱스 0, 'b'는 인덱스 1이 됩니다.
- 문자 빈도 감소 :
- 문자열 t의 각 문자에 대해 해당 문자의 빈도를 감소시킵니다.
- 증가한 s의 빈도와 감소한 t의 빈도가 정확히 일치해야 애너그램이 성립됩니다.
- 빈도 비교 :
- charCount 배열을 순회하면서 모든 값이 0인지 확인합니다.
- 하나라도 0이 아닌 값이 있다면 두 문자열은 애너그램이 아닙니다.
- 애너그램 확인 :
- 모든 빈도가 0이라면 두 문자열은 애너그램으로, true를 반환합니다.
시간 복잡도
- O(n) : 여기서 n은 문자열의 길이입니다.
- s와 t를 각각 한 번씩 순회하면서 문자의 빈도를 증가 및 감소하므로, 전체적으로 O(n)의 시간 복잡도를 가집니다.
공간 복잡도
- O(1) : 고정 크기 배열(26)을 사용하므로 상수 공간을 사용합니다.
- 알파벳의 개수는 고정되어 있어 입력 크기에 상관없이 공간 복잡도가 일정합니다.
