[Hashing] Maximum Number of Balloons

출처 :  leetcode - DS course

 

문제:

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible. You can use each character in text at most once. Return the maximum number of instances that can be formed.

 

Input: text = "nlaebolko"
Output: 1

Input: text = "loonbalxballpoon"
Output: 2

Input: text = "leetcode"
Output: 0

Constraints:

• 1 <= text.length <= 104
• text consists of lower case English letters only.

1) text 안에 들어있는 string에 주어진 char들을 찾는것.

2) Instance 라 함은 완성된 한 단어라는 의미로 풀이됨.  

 

---

풀이

일단 해설을 풀이해보자.  -> 굳이 hash를 쓴거같진않은데   Approach 1

 

1) b,a,l,o,n 5개의 character들을 분류하고 각 필요한 갯수를 카운터해준다.

The word balloonballoonballoon consists of five different characters with counts of {'b':1, 'a':1, 'l':2, 'o':2, 'n':1}.

2) frequency in balloon은 각 캐릭터들의 필요개수들이고

3) potential with x instances 는 balloon이라는 단어를 생성하기는 세트수

요런식으로 짤수있구나.

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;
        
        // Count the frequencey of all the five characters
        for (int i = 0; i < text.length(); i++) {
            if (text[i] == 'b') {
                bCount++;
            } else if (text[i] == 'a') {
                aCount++;
            } else if (text[i] == 'l') {
                lCount++;
            } else if (text[i] == 'o') {
                oCount++;
            } else if (text[i] == 'n') {
                nCount++;
            }
        }
        
        // Find the potential of each character.
        // Except for 'l' and 'o' the potential is equal to the frequency.
        lCount = lCount / 2;
        oCount = oCount / 2;
        
        // Find the bottleneck.
        return min({bCount, aCount, lCount, oCount, nCount});
    }
};

Time complexity

O(N) :We iterate over all the characters of string text which requires N operations.

Space complexity:

O(1) All we need is the 5 variables to store the frequency of characters. Hence the space complexity is constant.

 

*

std::min ({ } ,comp) 로 되어있는데 { } 만 써도 동작이되네?

https://blockdmask.tistory.com/366

[C++] 최초값, 최대값 함수 min, max 에 대해서 (클래스, vector 사용법까지)

 

- 수학문제처럼 꼭 직접 손으로 써보기 ! 

- 하루에 한문제씩 졸업떄까지 꾸준히.