383. 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를 구성 할 수 있는지 확인하는 문제이다.

사실 여러가지 방법으로 풀 수 있지만 해시테이블을 사용해서 풀었다.

 

magzine에 담긴 문자열을 for문으로 순회하며 나오는 알파벳의 개수를 딕셔너리에 넣고  이후에 ransomNote를 for문으로 순회하며 나오는 횟수마다 딕셔너리에서 차감해주었다.

 

딕셔너리 대신 아스키코드로 변환해서 리스트 안에 넣어서 만들어도 괜찮을거같다.

 

class Solution(object):
    def canConstruct(self, ransomNote, magazine):

        dict ={} 			# 알파벳 횟수를 넣을 딕셔너리 생성
        for i in magazine: 	# 사용 할 수 있는 알파벳배열, 
            if i not in dict: # 딕셔너리에 없다면 키 값으로 저장, 
                dict[i] = 1
            else:
                dict[i]+=1 # 딕셔너리에 있다면 키의 밸류 +1
        
        for i in ransomNote:  # 만들어야 할 알파벳 배열
            if i not in dict or dict[i]==0: # 딕셔너리에 존재하지않거나, 0이라면 False 반환
                return False
            dict[i]-=1  	  # 존재한다면 값 -1 
        
        return True

 

 

 

 

 

다른사람의 풀이

 

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        for i in set(ransomNote):
            if ransomNote.count(i) > magazine.count(i):
                return False
        return True

 

문자열을 set으로 중복이 없게 만든 후, for문으로 뽑아내어 각각 카운트함수를 통해 개수를 비교한다.

 

음.. 시간복잡도를 생각해봤는데,영어 소문자 26개로만 주어진 가정하에 한다면 비슷할 거 같다, 만일 다른 문자까지 합쳐진다면 해시테이블을 쓰는게 맞다고 생각한다.