Ransom Note - LeetCode
Can you solve this real interview question? Ransom Note - Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ranso
leetcode.com
두 문자열 ransomNote와 magazine이 주어졌을 때, magazine의 문자를 사용하여 ransomNote를 구성할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
magazine의 각 문자는 ransomNote에서 한 번만 사용할 수 있습니다.
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
문제접근
해시맵을 사용해서 풀고자 하였습니다.
해시의 메서드들은 O(1)의 시간복잡도를 갖고있기 때문에 공간복잡도를 어느정도 포기하고
시간복잡도면에서 좋은코드를 작성할 수 있습니다.
magazine의 각 문자를 map에 카운팅하고
ransomNote를 확인하면서 map에 값이 0이 아니라면 true
하나라도 0이 있다면 false를 반환하도록 하였습니다.
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < magazine.length(); i++) {
char key = magazine.charAt(i);
map.put(key, map.getOrDefault(key, 0) + 1);
}
for (int i = 0; i < ransomNote.length(); i++) {
char key = ransomNote.charAt(i);
if (map.containsKey(key) && map.get(key) > 0) {
map.put(key, map.get(key) - 1);
} else {
return false;
}
}
return true;
}
시간복잡도
O(n)의 시간복잡도가 필요합니다.
다른사람의 풀이
배열을 map처럼 사용한 풀이입니다.
public boolean canConstruct(String ransomNote, String magazine) {
int[] charCounts = new int[26]; // Assuming lowercase English letters
for (char c : magazine.toCharArray()) {
charCounts[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
if ( !(charCounts[c - 'a'] > 0 ) ) {
return false;
}
charCounts[c - 'a']--;
}
return true;
}
느낀점
해시맵을 사용하는 이유는 분명합니다.
조회, 삽입, 삭제가 O(1) 이라는 아주 효율적인 자료구조입니다.
반면 공간복잡도는 그만큼 잡아먹는다는것을 꼭 기억해야합니다.
참고
'LeetCode' 카테고리의 다른 글
[LeetCode] 150. Evaluate Reverse Polish Notation (0) | 2023.09.01 |
---|---|
[LeetCode] 242. Valid Anagram (0) | 2023.08.31 |
[LeetCode] 219. Contains Duplicate II (0) | 2023.08.31 |
[LeetCode] 1. Two Sum (0) | 2023.08.31 |
[LeetCode] 155. Min Stack (0) | 2023.08.30 |