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 ransomNote.

풀이

• magazine의 문자들로 ransomNote를 만들 수 있어야 한다.
• 둘다 소문자만 허용
• alphabet의 개수를 관리하는 int[26] 배열을 생성한다.
• magazine 문자열을 문자마다 개수를 계산한다.
• ransomNote에서 앞에서부터 하나씩 확인하면서 배열에 저장된 개수가 1이상이라면 개수를 줄이고 continue, 아니라면 false로 처리

수도 코드

alphabet = size가 26인 int 배열 생성

for magazine의 처음부터 끝까지:
	alphabet[magazine[i]]++

for ransomNote의 처음부터 끝까지:
	if alphabet[ransomNote[i]] > 0:
    	alphabet[ransomNote[i]]--
   	else  # 만들 수 없으므로 false 종료
    	return False
return True

Solution(Runtime: 3ms)

import java.util.*;


class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] alphabet = new int[26];

        for(int i = 0; i < magazine.length(); i++) {
            alphabet[magazine.charAt(i) - 'a']++;
        }

        for(int i = 0; i < ransomNote.length(); i++) {
            if (alphabet[ransomNote.charAt(i) - 'a'] > 0) {
                alphabet[ransomNote.charAt(i) - 'a']--;
                continue;
            }
            return false;
        }
        return true;
    }
}

• 다른사람의 풀이

from collections import Counter

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        c1, c2 = Counter(ransomNote), Counter(magazine)
        return c1 & c2 == c1

Counter는 산술 연산자를 사용할 수 있다. 객체를 더하거나(+) 객체를 뺼 수도(-)있다.
c1 & c2의 의미는 교집합으로 예를 들어

• ransomNote = "aa", magazine = "aab"일 때,
  c1 & c2는 Counter({'a': 2})의 값이 된다.

덕분에 Counter에서도 다양한 연산이 가능하다는 것을 알게 되었다! Set은 중복 문자열이 걸러지기 때문에, 여러개의 값이 들어올때 Counter를 활용하는 것도 좋을 듯하다.