LeetCode 383 Ransom Note

nayu1105·2023년 8월 31일

leetcode 알고리즘

LeetCode

목록 보기

20/28

LeetCode 383 Ransom Note 풀러가기

문제

문자열이 magazine, ransomNote 두개 주어진다.

magazine으로 ransomNote 문자열을 만들 수 있으면 true, 없으면 false를 반한하는 함수를 구현해라.

문제 분석

첫번째 시도

가장 간단히 생각해낸 방법은 magazine에 있는 것들을 다 hashmap에 <문자,갯수> 로 저장하는 것이였다.
그 후, 저장된 map으로 ransomNote를 만들 수 있는지 다시 검색하는 것이다.

이 알고리즘의 시간복잡도는 O(N^2)이였다.

코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0; i<magazine.length(); i++){
            map.put(magazine.charAt(i),map.getOrDefault(magazine.charAt(i),0)+1);
        }

        for(int i=0; i<ransomNote.length(); i++){
            if(map.containsKey(ransomNote.charAt(i))&&map.get(ransomNote.charAt(i))>0){
                map.put(ransomNote.charAt(i),map.get(ransomNote.charAt(i))-1);
            }else return false;
        }

        return true;

    }
}

결과 : 성공

Runtime

Memory

시간복잡도가 O(N^2)이다보니, 실행시간이 너무 길었다. 다른 방법을 고안해봐야겠다.

두번째 시도(시간 개선)

문제에서 문자열은 무조건 소문자로 주어진다고 했다.
그래서 map을 사용하지 않고, int 배열 26개로 사용하여 map에서 key값이 있는지, value값을 찾거나 변경하는 시간 등을 줄이려고 했다.

코드

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

        for(int i=0; i<magazine.length(); i++){
            count[magazine.charAt(i)-97]++;
        }

        for(int i=0; i<ransomNote.length(); i++){
            if(count[ransomNote.charAt(i)-97]>0)count[ransomNote.charAt(i)-97]--;
            else return false;
        }

        return true;

    }
}