-
leetcode top interview 150 | Ransom Note | HashMapPS 2023. 9. 1. 09:29
Question
ransomNote 문자열이 magazine에 있는 문자로만 구성되어있으면 true, 아니면 false 리턴
magazine에 있는 각각의 문자는 ransomNote에서 한번만 사용할 수 있다.
Accepted Code
import java.util.*; class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] alpha = new int[26]; for(char c : magazine.toCharArray()){ alpha[c - 'a']++; } for(char c : ransomNote.toCharArray()){ int idx = c - 'a'; if(alpha[idx] > 0) alpha[idx]--; else return false; } return true; } }
처음엔 magazine에 있는 문자를 한번만 사용할 수 있다고 해서 중복된 문자도 한번만 사용할 수 있다고 생각했었다. 하지만 그게 아니라
magazine이 "aaab"이고 ransomNote가 "aa"면 magazine에 있는 문자를 한번씩 사용해서 "aa"를 만들 수 있으므로 true를 리턴해야한다.
문자열이 알파벳으로만 이루어져 있으므로 26사이즈의 배열을 활용해 magazine의 문자 cnt개수를 저장해주고 randsomeNote의 문자들을 저장한 cnt에서 뺴줘서 만들 수 있는지 확인해줬다.
Accepted Code - HashMap
import java.util.*; class Solution { public boolean canConstruct(String ransomNote, String magazine) { Map<Character, Integer> map1 = new HashMap<>(); Map<Character, Integer> map2 = new HashMap<>(); for(char c : ransomNote.toCharArray()){ map1.put(c, map1.getOrDefault(c, 0) + 1); } for(char c : magazine.toCharArray()){ map2.put(c, map2.getOrDefault(c, 0) + 1); } for(Map.Entry<Character, Integer> entry : map1.entrySet()){ char c = entry.getKey(); int cnt = entry.getValue(); if(!map2.containsKey(c) || map2.get(c) < cnt) return false; } return true; } }
Solve
배열로 푸는게 익숙하지만 카테고리가 HashMap이라서 풀이법을 생각해봤다.
마찬가지로 magazine에 있는 문자가 ransomNote에서 한번만 사용할 수 있다는 조건때문에 각 문자의 개수까지 함께 저장해서 확인해줘야한다.
따라서 HashMap을 활용해 key를 문자로, value를 문자의 cnt 수로 저장해주고 ransomeNote에 있는 문자가 magazine에 있는지, magazine Map에 있는 해당 문자 cnt가 ransomeNote의 cnt보다 같거나 큰지를 확인하고 true를 리턴하도록 해줬다.
'PS' 카테고리의 다른 글
leetcode top interview 150 | Min Stack | ArrayList (0) 2023.09.01 leetcode top interview 150 | Valid Anagram | HashMap (0) 2023.09.01 leetcode top interview 150 | Contains Duplicate II | HashMap (0) 2023.09.01 leetcode top interview 150 | Evaluate Reverse Polish Notation | Stack (0) 2023.08.31 leetcode top interview 150 | Minimum Size Subarray Sum | Sliding window (0) 2023.08.29