구름톤 챌린지 1주차 - 2

2023.08.17.(목)

#include <stdio.h>
int main() {
    int N;
    scanf("%d", &N);
    
    int k[1002], max = 0, max_position = -1, sum = 0;
    for (int i=0; i<N; i++) {
        scanf("%d", &k[i]);
        sum += k[i];
        if (k[i] > max) {
            max = k[i];
            max_position = i;
        }
    }
    
    int notPerfect = 0;
    if (max_position == 0) {
        for (int i = max_position + 1; i<N; i++) {
            if (k[i] > k[i-1]) {
                notPerfect = 1;
                break;
            }
        }
    }
    else if (max_position == N-1) {
        for (int i = max_position - 1; i > -1; i--) {
            if (k[i] > k[i+1]) {
                notPerfect = 1;
                break;
            }
        }
    }
    else {
        for (int i = max_position + 1; i<N; i++) {
            if (k[i] > k[i-1]) {
                notPerfect = 1;
                break;
            }
        }
        for (int i = max_position - 1; i > -1; i--) {
            if (k[i] > k[i+1]) {
                notPerfect = 1;
                break;
            }
        }
    }
    
    if (notPerfect)
        printf("0");
    else
        printf("%d", sum);
}

최댓값이 있는 위치를 찾은 후 좌, 우로 훑으며 내림차순으로 잘 내려가는지 반복문으로 확인했습니다.

최댓값이 양쪽 끝에 있는 경우를 따로 처리해줬고, 내림차순으로 잘 내려가지 않는다면 notPerfect를 1로 설정해 0을 출력하도록 하였습니다.

 

 

 

---

2023.08.18.(금)

#include <stdio.h>

#define SIZE 500002

typedef struct element{
    int value;
    int numberOfBits;
} element;

// prototype of functions

int getNumberOfBits(int value);
void mergeSort(element numbers[], int r, int l, int (*comp)(element *a, element *b));
void merge(element numbers[], int r, int m, int l, int (*comp)(element *a, element *b));
int comp1(element *a, element *b);
int comp2(element *a, element *b);


int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    element numbers[SIZE];
    for (int i=0; i<N; i++) {
        scanf("%d", &(numbers[i].value));
        numbers[i].numberOfBits = getNumberOfBits(numbers[i].value);
    }
    
    // 문제 조건에 따라 일단 숫자를 기준으로 내림차순 정렬하고
    // 그 다음 비트 중 1의 수을 기준으로 정렬하도록 하였다.
    // 그러면 비트 수 내림차순으로 정렬되고, 같은 비트 개수를 가지면 숫자 내림차순으로 정렬된다!
    // merge sort는 stable sort이니 가능한 것
    mergeSort(numbers, 0, N-1, comp1);
    mergeSort(numbers, 0, N-1, comp2);
    
    printf("%d", numbers[K-1].value);
    
    return 0;
}

// Divide
void mergeSort(element numbers[], int r, int l, int (*comp)(element *a, element *b)) {  // r~l
    if (r<l) {
        int m = (r+l)/2;
        mergeSort(numbers, r, m, comp);
        mergeSort(numbers, m+1, l, comp);
        merge(numbers, r, m, l, comp);
    }
}

// Merge
void merge(element numbers[], int r, int m, int l, int (*comp)(element *a, element *b)) {  // [r,m], [m+1,l]
    element temp[SIZE];
    int i=r, j=m+1, k=0;
    for (; i<=m && j<=l;) {
        if (comp(&numbers[i], &numbers[j]))
            temp[k++] = numbers[i++];
        else
            temp[k++] = numbers[j++];
    }
    for (;i<=m;)
        temp[k++] = numbers[i++];
    for (;j<=l;)
        temp[k++] = numbers[j++];
    
    for (int x=r; x<=l; x++) {
        numbers[x] = temp[x-r];
    }
}

int getNumberOfBits(int value) {
    int result = 0;
    for (;value != 0; value/=2)
        if (value % 2 == 1)
                result++;
    return result;
}

int comp1(element *a, element *b) {
    return a->value >= b->value;  // '>'가 아니라 '>='로 비교해야 함!
}

int comp2(element *a, element *b) {
    return a->numberOfBits >= b->numberOfBits;  // '>'가 아니라 '>='로 비교해야 함!
}

비트 수를 세는 별도의 함수인 getNumberOfBits()를 구현하였고, 반복문에서 2로 나누며 비트 중 1의 개수를 세서 반환하도록 하였습니다.

비트 중 1의 개수를 기준으로 정렬해야하는데, 같은 개수를 가진다면 숫자 값 자체를 기준으로 정렬해야합니다. 그래서 stable sort를 이용해 일단 숫자 자체를 기준으로 내림 차순으로 정렬하도록 한 뒤, 비트 중 1의 수를 기준으로 정렬하도록 하였습니다.

즉, 두번 정렬하는데, 처음 정렬한 순서를 유지해야하므로 stable sort 중 하나인 merge sort를 구현하여 사용했습니다.

여기서 짚어볼만한 점은, 위 구현 방식의 merge sort가 stable sort가 되도록 하기 위해선 비교를 할 때 크다(>)가 아니라 크거나같다(>=)를 활용해야 한다는 것입니다. 그래야 두 값을 비교해서 같은 값일 때 왼쪽의 값이 먼저 들어가서 stable sort가 됩니다.

(mergeSort() 함수에서 comp 함수의 반환값을 1(크다),0(같다),-1(작다) 중 하나로 반환하게 해서 강제하는 식으로 구현했으면 일반화가 잘 됐을 것 같음. 지금 이 함수는 comp 함수 만들 때 실수로 그냥 '<' 이런거 써서 비교하면 stable sort가 안되니까 좀 더 강제하는 방식으로 구현하면 좋을 듯)