문제 링크
1. 아이디어
두 문자열 s와 t가 애너그램인지 판단하는 문제로 애너그램은 각 문자열을 이루는 개별 문자의 종류와 수가 모두 일치하는 경우다. 두 문자열이 모두 알파벳 소문자로 이루어져 있으므로 26칸의 카운팅 배열을 통해 s의 문자는 세고, t의 문자는 빼면 카운팅 배열의 모든 원소가 0인지 여부로 애너그램을 판별할 수 있다.
Follow up은 유니코드 문자들에 대해 애너그램 여부를 판단하는 상황이다. 유니코드는 범위가 훨씬 넓으므로 이 경우 카운팅 맵을 활용해 카운팅을 하면 카운팅 맵의 모든 값들이 0인지 여부로 애너그램을 판단할 수 있다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 카운팅 배열 | $O(N + M)$ | $O(1)$ |
| 카운팅 맵 | $O(N + M)$ | $O(N + M)$ |
($N$ = s의 길이, $M$ = t의 길이. 카운팅 배열은 소문자 26종에 묶여 입력 길이와 무관하게 상수 공간)
3. 코드
풀이 1: 카운팅 배열 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean isAnagram(String s, String t) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnt[c - 'a']--;
}
for (int x : cnt) {
if (x != 0) return false;
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> cnt(26);
for (char c : s) cnt[c - 'a']++;
for (char c : t) cnt[c - 'a']--;
for (int x : cnt) {
if (x != 0) return false;
}
return true;
}
};
|
1
2
3
4
5
6
| from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
|
풀이 2: 카운팅 맵 [Java][C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import java.util.*;
class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> cnt = new HashMap<>();
for (char c : s.toCharArray()) {
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
cnt.put(c, cnt.getOrDefault(c, 0) - 1);
}
for (Map.Entry<Character, Integer> e : cnt.entrySet()) {
if (e.getValue() != 0) return false;
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> cnt;
for (char c : s) cnt[c]++;
for (char c : t) cnt[c]--;
for (auto [_, v] : cnt) {
if (v) return false;
}
return true;
}
};
|