LeetCode 1431. Kids With the Greatest Number of Candies

 

접근 오류

❗️처음에 생각한 방향

모든 배열에 대해 하나하나 계산해보려고 함

 

먼저 index 역할을 하는 i에 대해 for문을 돌려

candies[i] + extraCandies 한 것이 배열의 나머지 모든 요소들보다 큰 지 isGreatest로 총 n번 확인

 

isGreatest의 구성은,

max로 주어진 parameter (여기선 index라고 표시)를 for문을 돌려 또 다시 candies 배열의 모든 요소와 비교

 

 

⛔️ 위와 같이 할 경우, 쓸데없는 계산이 늘어 시간복잡도가 O(n^2) 됨

int isGreatest(int* candies, int candiesSize, int index){
    for(int i=0; i<candiesSize; i++){
        if(candies[i] > index) return 0; //false
    }
    return 1; //true
}

bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){
    *returnSize=candiesSize;
    bool* result = (bool*) malloc((*returnSize)*sizeof(bool));

    for(int i=0; i<candiesSize; i++){
        if(isGreatest(candies, candiesSize, candies[i]+extraCandies)==1)
        	result[i] = true;
    	else if(isGreatest(candies, candiesSize, candies[i]+extraCandies)==0) 
    		result[i] = false;
    }
    
    return result;
}

 

접근

✅  최종적으로 extraCandies는 배열 원소 중 하나에만 더해줄 것이므로,

       먼저 그냥 배열에서 제일 큰 값인 max를 찾은 뒤, 

       해당 max 값과 candies[i]+extraCandies 값과 비교해서

       max <= candies[i]+extraCandies 이면 true,

       아니면 false를 배열에 반환

 

 

구현

시간복잡도 : O(n)

for문이 중첩되어 있지 않고 따로따로 2개가 있기 때문에 위의 구현보다 시간복잡도 감소

bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){
    *returnSize=candiesSize;
    bool* result = (bool*) malloc((*returnSize)*sizeof(bool));

    int max=candies[0];

    for(int i=0; i<candiesSize; i++){
        if(candies[i] > max) max = candies[i];
    }

    for(int i=0; i<candiesSize; i++){
        if(candies[i]+extraCandies >= max) result[i] = true;
        else result[i]=false;
    }

    return result;
}

 

Take aways

✅ 일단 문제에 주어진 parameter는 사용하려고 해보자

     - returnSize가 굳이 주어졌다면 코드의 깔끔함을 위해 return array의 malloc은 returnSize로 할 것.

    *returnSize=candiesSize;
    bool* result = (bool*) malloc((*returnSize)*sizeof(bool));

 

✅ 1차적으로 변하지 않는 고정값을 찾을 수 있으면 계산의 간단함을 위해 1단계를 먼저 시작

     - max를 먼저 찾으면, 동일한 array의 max는 항상 고정되어 있으므로 max를 찾고 이후 계산은 한 번에 비교 가능

 

✅ C언어(C99)도 boolean Type을 지원해준다

    - 다만, <stdbool.h> header 추가 필수 ( #include <stdbool.h> )