참고
문제해설
NOTE
•
입력 값 ⇒ ransomNote, magazine 이름의 2개 문자열
•
출력 값 ⇒ magazine 문자열로 ransomNote를 만들 수 있는지에 대한 여부
•
2개 문자열 모두 소문자로 구성된다.
문제 로직고민
NOTE
•
풀이 방법이 바로 보였는데, 각 문자열마다 알파벳 개수를 저장하는 Map을 생성하고 magazine쪽이 ransomNote의 모든 알파벳의 개수보다 많으면 true이다.
◦
2개의 문자열을 char[]로 변환시킨 이후, 각 문자열의 알파벳의 개수를 Map을 통해 저장한다.
◦
ransomeNote의 알파벳 개수를 저장한 Map의 key를 순회하면서, ransomNote가 해당 알파벳을 가지고 있는지, 개수는 더 많은지 확인한다.
◦
모두 만족한다면 true, 중간에 만족하지 않는경우 false;
작성코드
NOTE
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> ransomNoteMap = new HashMap();
HashMap<Character, Integer> mazaineMap = new HashMap();
for(char c : ransomNote.toCharArray()){
if(!ransomNoteMap.containsKey(c)) ransomNoteMap.put(c, 1);
else ransomNoteMap.put(c, ransomNoteMap.get(c) + 1);
}
for(char c : magazine.toCharArray()){
if(!mazaineMap.containsKey(c)) mazaineMap.put(c, 1);
else mazaineMap.put(c, mazaineMap.get(c) + 1);
}
for(Map.Entry<Character, Integer> entry : ransomNoteMap.entrySet()){
char key = entry.getKey();
int value = entry.getValue();
if(!mazaineMap.containsKey(key) || mazaineMap.get(key) < value) return false;
}
return true;
}
}
Java
복사
정답코드
NOTE
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] magCnt = new int[256];
for(char c: magazine.toCharArray()) {
++magCnt[c];
}
for(char c: ransomNote.toCharArray()) {
if(magCnt[c] == 0) {
return false;
}
--magCnt[c];
}
return true;
}
}
Java
복사
시간이 빠른 코드
•
내가 생각한 로직과 비슷하지만 더 효율적이다. 위와같이 진행하면 2번의 반복으로 끝나기 때문이다.
•
또한 Map구조를 사용하지 않고 단순 배열로 해결한점도 눈에뛴다. 어차피 모든 문자열은 소문자영어 이므로 26크기의 char로 처리가 된다.
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] map = new int[26];
for(char x: magazine.toCharArray()){
map[x - 'a'] += 1;
}
for(char x: ransomNote.toCharArray()){
map[x - 'a'] -= 1;
if(map[x - 'a'] == -1){return false;}
}
System.gc();
return true;
}
}
Java
복사
메모리가 효율적인 코드
•
위에서 작성한 코드에서 map크기를 최소값인 26으로 맞추고 System.gc()가 추가되었다.