Leetcode 1419) Minimum Number of Frogs Croaking

20 May 2021 in Algorithms

• 순서대로니까, (c가 나타난 총 수 >= r가 나타난 총 수 >= o가 나타난 총 수>= a가 나타난 총 수 >= k가 나타난 총 수) 면 된다.
• availableFrog라는 변수는, croak이 끝날 때(k일 때) 증가되고, croak이 시작 될 때(c일 때) 감소된다.
• for문을 다 돌고 나와서 c,r,o,a,k 숫자가 맞으면 된다.

class Solution {            
    public int minNumberOfFrogs(String croakOfFrogs){
        int numFrog=0;
        int availableFrog = 0;
        int numCroak = croakOfFrogs.length()/5;
        boolean[][] frogs= new boolean[numCroak][5];
        //맨 처음에 거르는 편하게 조건
        if(croakOfFrogs.length()%5!=0){
            return -1;
        }
        int c = 0;int r=0; int o =0; int a = 0;int k=0;
        String croak = "croak";
        for(int i =0;i<croakOfFrogs.length();i++){
            switch (croakOfFrogs.charAt(i)){
                case 'c': c++;
                    if(availableFrog==0){
                        numFrog++;
                    }else{
                        availableFrog--;
                    }
                    break;
                case 'r': r++;
                    if(c<r){
                        return -1;
                    }
                    break;
                case 'o': o++;
                    if(r<o){
                        return -1;
                    }
                    break;
                case 'a': a++;
                    if(o<a){
                        return -1;
                    }
                    break;
                case 'k': k++;
                  if(a<k){
                        return -1;
                    }
                    availableFrog++;
                    break;
                default:
                    return -1;
            }
        }


        if(c==r && r==o && o==a && a==k){
            return numFrog;
        }else{
            return -1;

        }
    }
}

//time limit exceeded! 처음 풀이.

• 이것보다 더 단순하게 위처럼 풀면된다.

class Solution {        
    public boolean repeat(int numCroak,int pos,boolean[][] frogs){
        for(int j=0;j<numCroak;j++){
            if(frogs[j][pos]==false && frogs[j][pos-1]==true){
                frogs[j][pos]=true;
                return false;
            }
            if (j==numCroak){
                return true;}
        }
        return true;
    }
    
    public int minNumberOfFrogs(String croakOfFrogs){
        int numFrog=0;
        int availableFrog = 0;
        int numCroak = croakOfFrogs.length()/5;
        boolean[][] frogs= new boolean[numCroak][5];
        //맨 처음에 거르는 편하게 조건
        if(croakOfFrogs.length()%5!=0){
            return -1;
        }

        String croak = "croak";
        for(int i =0;i<croakOfFrogs.length();i++){
            switch (croakOfFrogs.charAt(i)){
                case 'c': 
                    if(availableFrog==0){
                        numFrog++;
                    }
                    for(int j=0;j<numCroak;j++){
                        if(frogs[j][0]==false ){
                            frogs[j][0]=true;
                            if(availableFrog!=0){
                                availableFrog--;
                            }
                            break;
                        }
                        if (j==numCroak){
                            return -1;}}
                    break;
                case 'r': boolean a=repeat(numCroak,1,frogs);
                    if(a){
                        return -1;
                    }
                    break;
                case 'o': a=repeat(numCroak,2,frogs);
                    if(a){
                        return -1;
                    }
                    break;
                case 'a': a=repeat(numCroak,3,frogs);
                    if(a){
                        return -1;
                    }
                    break;
                case 'k': a=repeat(numCroak,4,frogs);
                    if(a){
                        return -1;
                    }
                    availableFrog++;
                    break;
                default:
                    return -1;
            }
        }
        return numFrog;
    }
}

다른 풀이

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        
        int count = 0;
        int c = 0;
        int r = 0;
        int o = 0;
        int a = 0;
        int k = 0;
        
        for(char ch : croakOfFrogs.toCharArray()){
            
            switch(ch){
                case 'c' : 
                    c++; 
                    break;
                case 'r' : 
                    r++; 
                    if(r > c) {return -1;} 
                    break; 
                case 'o' : 
                    o++; 
                    if(o > r) {return -1;} 
                    break;
                case 'a' : 
                    a++; 
                    if(a > o) {return -1;} 
                    break;
                case 'k' : 
                    k++; 
                    if(k > a) {return -1;} 
                    //아, 여기서는 availableFrog대신 이렇게 했다.
                    //기존 c가 등장한 개수 vs 이번에 c가 등장한 개수 둘 중 큰 걸 count에 저장. 
                    count = Math.max(count,c);
                    c--;r--;o--;a--;k--;
                    break;
            }
                
        }
        if(c != 0 || r != 0 || o != 0 || a != 0 || k != 0) return -1;
        
        return count;
    }
}