두 문자열 s와 t가 주어지면 t가 s의 애너그램이면 참을 반환하고, 그렇지 않으면 거짓을 반환합니다.
애너그램은 다른 단어 또는 구의 글자를 재배열하여 만든 단어 또는 구문으로, 일반적으로 원래 글자를 모두 정확히 한 번 사용합니다.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
문제접근
해시맵을 이용해 접근하였습니다.
중요한것은 s와 t의 길이가 같지않으면 false라는 것입니다.
나머지는 map을 이해하고있다면 크게 어렵지 않습니다.
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
HashMap<Character, Integer> map = new HashMap<>();
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
char key = s.charAt(i);
map.put(key, map.getOrDefault(key, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char key = t.charAt(i);
if (map.containsKey(key) && map.get(key) > 0) {
cnt++;
map.put(key, map.get(key) - 1);
}
}
System.out.println("s.length() <= cnt : " + s.length() + " " + cnt);
return s.length() == cnt;
}
시간복잡도
해시맵을 사용하고 있고, for-loop를 한번 돌고있습니다.
O(n)의 시간복잡도를 갖고있습니다.
다른사람의 풀이
sort를 이요해 정렬하고, equals메서드를 사용해서 간단하게 풀이한 코드입니다.
public boolean isAnagram(String s, String t) {
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
Arrays.sort(sChars);
Arrays.sort(tChars);
return Arrays.equals(sChars, tChars);
}
시간복잡도
Arrays의 sort는 DualPivotQuicksort를 사용하고있습니다.
O(n log(n))의 시간복잡도를 소요합니다.
그리고 Arrays.equals는 O(n)의 시간복잡도를 소요합니다.
따라서 위 로직의 시간복잡도는 O(n log(n))입니다.
느낀점
문제를 어떻게 접근하냐에 따라 문제풀이법이 달라지고
코드의 가독성이 달라진다는것을 알았습니다.
효율적인 코드와 가독성있는 코드를 작성하기위해 노력하겠습니다.
참고
✅3 Method's 🤯 || C++ || JAVA || PYTHON || Beginner Friendly🔥🔥🔥 - Valid Anagram - LeetCode
View kshatriyas's solution of Valid Anagram on LeetCode, the world's largest programming community.
leetcode.com
'LeetCode' 카테고리의 다른 글
[LeetCode] 148. Sort List (0) | 2023.09.02 |
---|---|
[LeetCode] 150. Evaluate Reverse Polish Notation (0) | 2023.09.01 |
[LeetCode] 383. Ransom Note (0) | 2023.08.31 |
[LeetCode] 219. Contains Duplicate II (0) | 2023.08.31 |
[LeetCode] 1. Two Sum (0) | 2023.08.31 |