리트코드 - 383. Ransom Note

리트코드 - 383. Ransom Note

출처 - https://leetcode.com/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 개의 문자열 ransomNote와 magazine이 주어졌을 때, ransomNote를 magazine의 문자들을 이용하여 구성할 수 있는 경우에는 true를 반환하고, 그렇지 않은 경우에는 false를 반환합니다.

magazine의 각 문자는 ransomNote에서 한 번만 사용될 수 있습니다.

 

의사코드

ransomMap 생성 magazineMap 생성 반복문 시작 [ransomNote 길이만큼 순회]     ransomMap에 key=알파벳, value=갯수만큼 더함 반복문 종료 반복문 시작 [magazine 길이만큼 순회]     magazineMap key=알파벳, value=갯수를 더함 반복문 종료 반복문 시작[ransomMap순회]     if (magazineMap 의 key에 ransomeMap으로 조회시 value가 null 또는 작은 경우)         false 리턴 반복문 종료 true 리턴

 

풀이코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> ransomMap = new HashMap<>();
        Map<Character, Integer> magazineMap = new HashMap<>();

        for (int i = 0; i < ransomNote.length(); i++) {
            char data = ransomNote.charAt(i);
            ransomMap.put(data, ransomMap.getOrDefault(data, 0) + 1);
        }
        for (int i = 0; i < magazine.length(); i++) {
            char data = magazine.charAt(i);
            magazineMap.put(data, magazineMap.getOrDefault(data, 0) + 1);
        }
        
        for (Map.Entry<Character, Integer> entry : ransomMap.entrySet()) {
            if (magazineMap.get(entry.getKey()) == null || entry.getValue() > magazineMap.get(entry.getKey())) {
                return false;
            }
        } 
        return true;
    }
}

코드설명

Map 2개를 이용해서 푸는 방법이다.

ransomMap과 magazineMap을 만들어서 각각 문자열을 순회하며 알파벳의 갯수를 넣는다.

 

그리고 ransomMap을 entrySet으로 변환하여 순회하면서 value값을 magazineMap에서의 value 값과 비교한다.

만일 value가 null이거나 작은 경우 false를 리턴한다.

 

위 경우를 모두 통과한 경우 true를 리턴한다.

 

시간복잡도 - O(n)

공간복잡도 - O(1) (최악의 경우 알파벳 크기만큼이나 상수이므로 무시)

 

문제를 풀며 생각한 흐름과 배운 점

이번에는 빠르게 풀어보는 것을 연습해보고자 했다.

 

처음 코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        String[] ransomArr = ransomNote.split("");
        String[] magazineArr = magazine.split("");

        Arrays.sort(ransomArr);
        Arrays.sort(magazineArr);

        for (int i = 0; i < ransomArr.length; i++) {
            if (!ransomArr[i].equals(magazineArr[i])) {
                return false;
            }
        }
        return true;
    }
}

그래서 단순하게 string을 배열화하여 알파벳을 정렬하고 배열값을 비교한다고 생각했다.

하지만 예외케이스가 너무 많았다. 충분히 고려할 수 있었는데 시간을 정하고 풀다보니 미처 생각못한 케이스가 있었다.

 

실패케이스

예를 들어 이런 경우다.

ransomNote에 있는 값이 magazine에는 그것보다 같거나 많기만 하면 된다.

그래서 위 풀이코드처럼 map을 두 개 만들어서 똑같이 비교하는 아이디어를 적용했는데....

생각보다 runtime 시간이 길고, 메모리도 많이 잡아먹는 것 같았다.

 

리팩토링

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> ransomMap = new HashMap<>();

        for (char data : ransomNote.toCharArray()) {
            ransomMap.put(data, ransomMap.getOrDefault(data, 0) + 1);
        }
        for (char data2 : magazine.toCharArray()) {
            int count = ransomMap.getOrDefault(data2, 0);
            if (count == 0) {
                continue;
            }

            ransomMap.put(data2, count - 1);
        }
        for (int count : ransomMap.values()) {
            if (count > 0) {
                return false;
            }
        }
        return true;
    }
}

map을 두 개만들지 말고 ransomMap만 만들어서 magazine을 순회하는 방법으로 변경했다.

향상된 for문으로 사용하여 가독성을 높였고, magazine을 순회하며 count 갯수를 하나씩 줄이는 방법으로 변경했다.

이렇게하니 런타임은 절반으로 줄었다.

다른코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCounts = new int[26]; // Assuming lowercase English letters
        
        for (char c : magazine.toCharArray()) {
            charCounts[c - 'a']++;
        }

        for (char c : ransomNote.toCharArray()) {
            if ( !(charCounts[c - 'a'] > 0 ) ) {
                return false;
            } 
                charCounts[c - 'a']--;
        }
        
        return true;
    }
}

map을 사용하지 않고, int 배열을 활용하고 있다.

기본적인 아이디어는 비슷하지만 런타임이 1ms 이다. (메모리는 비슷)

 

연속적이지 않은 map에 비해 주소값의 연속성을 띄는 배열인지라 속도가 더 빠른 것 같다.

 

정리

어디를 기준점으로 잡느냐에 따라 로직의 길이와 풀이속도가 달라지는 것 같다.

처음 코드에서 쓸데없이 Map을 두 개나 썼는데, 처음에 의사코드를 적거나 방법을 떠올리는 과정을 좀 더 깊게 생각해 봐야겠다.