CosPro1급 모의고사 - Part.3 함수 작성 - 숫자 뽑기 (C언어)

Cos Pro 1급 모의고사 - 숫자뽑기 에 대한 C언어를 이용한 저의 풀이입니다.

 

목차

• 문제 설명
• 매개변수 설명
• return 값 설명
• 예제
• ***풀이 전략***
• 문제와 답

 

문제 설명

자연수가 들어있는 배열에서 숫자 K개를 선택하려 합니다. 이때, 선택한 숫자 중 가장 큰 수와 가장 작은 수의 차이가 최소가 되도록 해야합니다.

예를 들어 배열에 들어있는 숫자가 [9, 11, 9, 6, 4, 19] 이고, K = 4 라면

• 숫자 4개를 [9, 11, 9, 6]로 뽑으면 (가장 큰 수 - 가장 작은 수) = (11 - 6) = 5가 됩니다.
• [9, 9, 6, 4] 와 같이 숫자를 뽑아도 (가장 큰 수 - 가장 작은 수) = (9 - 4) = 5가 됩니다.

그러나 가장 큰 수와 가장 작은 수의 차이가 5보다 작아지도록 숫자 4개를 선택하는 방법은 없습니다.

자연수가 들어있는 배열 arr, arr의 길이 arr_len, 선택해야 하는 숫자 개수 K가 매개변수로 주어질 때, 선택한 숫자중 가장 큰 수와 가장 작은 수의 차이가 최소가 되록 arr에서 숫자 K개를 선택했을 때, 그때의 가장 큰 수와 가장 작은 수의 차이를 return 하도록 solution 함수를 완성해주세요.

 

매개변수 설명

자연수가 들어있는 배열 arr, arr의 길이 arr_len, 선택해야 하는 숫자 개수 K가 solution 함수의 매개변수로 주어집니다.

• arr_len은 5 이상 1,000 이하입니다.
• arr의 원소는 1 이상 10,000 이하인 자연수입니다.
• K 는 4 이상 50 이하인 자연수입니다.

 

return 값 설명

선택한 숫자중 가장 큰 수와 가장 작은 수의 차이가 최소가 되도록 arr에서 숫자 K개를 선택했을 때, 그때의 가장 큰 수와 가장 작은 수의 차이를 return 해주세요.

예제

arr	arr_len	K	return
[9,11,9,6,4,19]	6	4	5

 

문제와 답

 

// 다음과 같이 include를 사용할 수 있습니다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
int solution(int arr[], int arr_len, int K) {
    // 여기에 코드를 작성해주세요.
    int answer = 0;
    int* sort = (int*) malloc(sizeof(int) * arr_len);
    // 최댓값 찾아오기 & 정렬할거 넣기
    for (int i = 0; i < arr_len; i++){
        answer = (answer > arr[i]) ? answer : arr[i];
        sort[i] = arr[i];
    }
    // 정렬하기
    for (int i = 0; i < arr_len; i++){
        int no_ordering = 0;
        for (int j = 0; j < arr_len-1; j++){
            if (sort[j] < sort[j+1])
            {   // 크면 앞으로
                int tmp = sort[j+1];
                sort[j+1] = sort[j];
                sort[j] = tmp;
            }
            else
                no_ordering += 1;
        }
        if (no_ordering == (arr_len-1))
            break; // 다 정렬하면 나와
    }
    // 큰 수 정렬에서 4칸씩 비교해보면..
    for (int i = 0; i < arr_len - (K-1); i++)
    {
        int diff = (sort[i] - sort[i+(K-1)]);
        if (diff < 0)
            diff = - diff;
        answer = (answer > diff) ? diff : answer;
    }
    return answer;
}
 
// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    int arr[] = {9, 11, 9, 6, 4, 19};
    int arr_len = 6;
    int K = 4;
    int ret = solution(arr, arr_len, K);
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret);
}

 

풀이 전략

뽑았을 때 가장 큰 수와 작은 수의 차이를 구하자고 배열을 다 뽑아서 계산할 순 없다.

대신, 가장 큰 수와 작은 수를 구분한다고 하면 값의 크기별로 정렬하면 편하지 않을까?

크기로 배열을 정렬하면 임의로 K개 만큼 뽑은 배열에서 가장 큰 수와 작은 수의 차이는

결국 크기 순서대로 있을 때의 K 칸만큼 떨어져 있는 수와 비교하면 될 것 같다.

 

내가 세운 절차는 다음과 같다.

1. 배열의 최댓값을 answer에 넣어서 일단 가장 크게 만들어준다.
2. 배열의 값을 크기별로 정렬한다.
3. 이때 n 칸과 n+k-1 칸 (1 ~ 4 칸?)을 비교한다.