Ransom Note

문제

두 문자열 ransomNote와 magazine이 주어질 때, ransomNote를 magazine의 문자들을 사용하여 만들 수 있다면 true를 반환하고 그렇지 않다면 false를 반환하세요. magazine의 각 문자는 ransomNote에서 한 번만 사용될 수 있습니다.

접근 방향

magazine에 있는 단어를 한 번씩만 사용하여 ransomNote를 만들 수 있어야 하므로 먼저 ransomNote 문자열을 순회하면서 한 글자씩 반복할 때마다 반복 횟수를 늘려서 글자를 키로 갖고 반복 횟수를 값으로 갖도록 map 자료형에 할당하고 magazine를 순회하면서 글자가 map 자료형의 키와 동일할 경우 밸류인 반복횟수를 1씩 차감하도록 한다. 모두 종료되었을 때 반복 횟수가 하나라도 남아있다면 즉, 어떤 글자던지 반복 횟수가 0보다 클 경우 magazine에 있는 글자로 ransomNote 글자를 만들지 못했다는 것을 의미하므로 False를 반환하고 그렇지 않을 경우 True를 반환하도록 한다.

나의 풀이

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # 이전 문제에서 다른 사람의 풀이에서 본 아이디어를 활용하여
        # ransomNote를 세트 자료형으로 만든 후의 길이와 magazine의 길이가 동일하다면
        # 두 글자 사이에 중복된 글자가 존재하지 않는 것이므로 False를 반환
        if len(set(ransomNote)) == len(magazine):
            return False

        # 알파벳(글자)을 키로 갖는 map 자료형 생성
        alphaMap = {}

        # ransomNote 문자열을 한 글자씩 순회
        for value in ransomNote:
            # 글자가 이미 키로 존재할 경우 반복횟수를 나타내는 밸류값을 1 증가
            if value in alphaMap:
                alphaMap[value] += 1
            # 그렇지 않을 경우, 키와 값 할당
            else:
                alphaMap[value] = 1

        # magazine 문자열을 한 글자씩 순회하여 중복 요소 확인
        for value in magazine:
            # 중복될 경우 1차감
            if value in alphaMap:
                alphaMap[value] -= 1

        # map의 밸류를 순회하여 값이 0보다 클 경우
        # 중복되지 않아 차감되지 않은 것이므로 False를 반환
        for i in alphaMap.values():
            if i > 0:
                return False

        return True

다른 사람의 풀이

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        # magazine의 글자보다 ransomeNote 글자 길이가 더 길다면 False 반환
        # 이 경우 magazine의 글자로 ransomNote의 글자를 만들 수 없는 것을 의미
        if len(ransomNote) > len(magazine): return False

        # ransomNote 문자열을 세트 자료형으로 변환하여 유니크한 값만 추출
        for x in set(ransomNote):
            # 각각의 유니크한 값을 ransomeNote가 더 많이 가지고 있을 경우
            # magazine 단어로 ransomNote를 만들 수 없으므로 False 반환
            if ransomNote.count(x) > magazine.count(x): return False

        return True

이 문제의 핵심은 ransomNote의 각 단어를 magazine이 중복으로 가지고 있을 경우 True를 반환하고 그렇지 않을 경우 False를 반환하는 것이므로 ransomNote의 유니크한 값을 추출하여 이 유니크한 값을 ransomNote가 더 많이 가지고 있을 경우 magazine의 단어가 유니크한 값을 갖는 중복 횟수가 ransomNote 글자를 만들기에 부족하다는 의미이므로 위와 같은 로직을 확인할 수 있었다.

# ransomNote = "aa"
# magazine = "aab"

ransomNote의 유니크한 값: a
ransomNote.count(a) = 2
magazine.count(a) = 2

# 동일하므로 magazine의 단어들로 ransomNote를 만들 수 있다.

# ransomNote = "aaa"
# magazine = "aab"

ransomNote의 유니크한 값: a
ransomNote.count(a) = 3
magazine.count(a) = 2

# ransomNote가 갖는 수가 더 크므로 magazine의 단어들로 ransomNote를 만들 수 없다.