[ 알고리즘 ] LeetCode 383. Ransom Note

이주 weekwith.me·2022년 8월 26일

목록 보기

70/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 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 .

제약사항

1 <= ransomNote.length, magazine.length <= 10^5
ransomNote and magazine consist of lowercase English letters.

풀이

접근법

해시 테이블 -파이썬에서의 딕셔너리- 을 사용해서 문자를 키로 개수를 값으로 저장한 다음 이를 비교하여 문제를 해결할 수 있다.

나의 풀이

입력값 ransomNote 를 기준으로 해시 테이블을 만들면 아래와 같이 문제를 해결할 수 있다.

def solution(ransomNote: str, magazine: str) -> bool:
    characters: dict[str, int] = {}
    for character in ransomNote:
        if character in characters:
            characters[character] += 1
        else:
            characters[character] = 1
    
    for character in magazine:
        if character in characters and characters[character] > 0:
            characters[character] -= 1
        
    return True if sum(characters.values()) == 0 else False

다른 풀이

입력값 magazine 을 기준으로 해시 테이블을 만들면 조금 더 단순하게 문제를 해결할 수 있다.

def solution(ransomNote: str, magazine: str) -> bool:
    characters: dict[str, int] = {}
    for character in magazine:
        if character in characters:
            characters[character] += 1
        else:
            characters[character] = 1
    
    for character in ransomNote:
        if character not in characters or characters[character] == 0:
            return False
        else:
            characters[character] -= 1
        
    return True