LeetCode 1679. Max Number of K-Sum Pairs

 

⭐️ 이 문제 다시 풀어보기 ⭐️

 

 

초기 접근 방법

❗️처음에 생각한 방향

 

일단 주어진 배열의 수가 k보다 크면 볼 필요 없으니 if 문으로 조건을 한 번 걸고,

서로 다른 두 수를 더해야하니 i != j 가 다른 조건도 걸어 두 번의 for문을 중첩.

처음에는 시간 복잡도를 생각하지 않고 brute force로라도 코드 구현해봄.

 

 

 

 

Brute Force

int maxOperations(int* nums, int numsSize, int k){
    int ret=0;
    
    for(int i=0; i<numsSize; i++){
        if(nums[i] < k){
            for(int j=0; j<numsSize; j++) {
                if (nums[j] < k && i != j){
                    if(nums[i] + nums[j] == k){
                        nums[i] = nums[j] = 0;
                        ret++; break;
                    }
                }
                else continue;
            }   
        }
        else continue;
    }
    return ret;
}

 

일단 시간복잡도를 생각하지 않고 생각나는 대로 구현해봄.

짜면서도 좋지 않다고 생각했고 역시나 42 / 51 번째 Testcase에서 Time Limit Exceeded 이 뜨는 것을 확인할 수 있음 

 

 

✏️ 어떻게 접근하면 될까 하다 일단 Two Pointers 로 접근해보자 생각하게 됨

 

 

 

최종 접근

사실 알고리즘 코딩 문제를 처음 푸는 거라 혼자 계속 생각하다가

결국 다른 분이 구현한 코드를 참고하기함..

나중에 잊을 때쯤 다시 풀어볼 문제

 

✅ 문제에서 주어진 배열은 무작위 배열 : 즉, 오름차순 또는 내림차순 아님 

그렇기 때문에 오름차순으로 정렬해줄 것

 

✅ 오름차순으로 정렬해주는 이유는 순서가 정해지면, 다시 인덱스 돌아가지 않아도 됨

 

 

✅ 오름차순 정렬을 하고, Two pointer를 양 끝에 두고 구현하면 됨

 

 

✅ 정렬 시, 다행히도 C언어에서 제공해주는 qsort가 있음

 

 

구현

Runtime : 103ms

Beats 96.33% of users with C

int compare(const void *a, const void *b)    
{
    int num1 = *(int *)a;   
    int num2 = *(int *)b;   

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}

int maxOperations(int* nums, int numsSize, int k){
    int ret=0;
    int l=0, r=numsSize-1;

    qsort(nums, numsSize, sizeof(int), compare);

    while(l < r){
        if(nums[l]+nums[r] == k) {
            l++;
            r--;
            ret++;
        }
        else if(nums[l]+nums[r] > k) r--;
        else l++;
    }
    return ret;

}

 

 

 

Take aways

✅ C언어 <stdlib.h>을 통해 주어진 배열을 quick sort 정렬 해줌

<stdlib.h> : qsort가 정의된 헤더 파일

void qsort (void *base, size_t n, size_t type_size, int (*compare)(const void *, const void *);

qsort(정렬할메모리주소, 요소개수, 요소크기, 비교함수);

먼저 qsort 함수를 사용하기 전에 비교(compare) 함수를 만들어야 하고, qsort를 사용하기 위한 약속으로 사용하는 함수 있음.

• a < b일 때는 -1을 반환
• a > b일 때는 1을 반환
• a == b일 때는 0을 반환

위 규칙에 따른 비교 함수여야 함.

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return -1;      // -1 반환
    
    if (num1 > num2)    // a가 b보다 클 때는
        return 1;       // 1 반환
    
    return 0;    // a와 b가 같을 때는 0 반환
}

int compare(const void *a, const void *b)
{
    return *((int *)a) - *((int *)b);
}

오름차순의 경우, 위와 같이 구현 가능.

 

 

 

✅ Quick sort : in-place sorting

즉, 정렬할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬 진행

 

 

✅ 배열이 주어지는 경우, 특히 무작위로 주어진다면

문제를 풀기위해 정렬이 필요한 지 생각해보기!!

정렬만 되어도 쉽게 풀리는 문제가 많기 때문에.