[C++] 프로그래머스 COS Pro 1급 숫자 뽑기

https://programmers.co.kr/learn/courses/11114/lessons/70745

COS Pro 1급 C++ 모의고사 - 숫자 뽑기

 

1. 서론

 

그냥 구현 문제인데... ㅎㅎ 역시나 내공부족으로 별로 어렵지도 않은 문제를 30분이나 붙잡았다.

 

2. 문제 풀이

 

자연수가 들어있는 배열이 있다. 이 배열에서 K개의 숫자를 선택해서 이 K개의 숫자들 중 가장 큰 수에서 가장 작은 수의 차가 가장 작은 값을 구하는 문제이다. 

 

딱 봤을 때 간단한 문제라서 엄청 단순하게 생각했다. 그냥 배열을 정렬하고 K-1번 값이랑 0 값을 빼면 가장 작은 수가 아닐까?라고.

왜냐하면 정렬을 통해서 작은 수들로 추렸고 그중에서 제일 큰 수와 작은 수를 빼는 거라서 가장 작은 값이 당연히 나올거라고 생각했는데 아니었다. 물론 이렇게 했을 때 답이 맞을 수도 있지만 결국엔 두 숫자 사이의 차가 가장 작아야 하는 것이기 때문에 그게 아니었다.

 

 

 

 

ex) 1 2 3 5 5

=> 5 - 1 > 5 - 5

 

ex) 1 3 5 9 100

=> 100 - 1 > 100 - 9

 

결국 중요한 것은 두 수의 차이이다. 하지만 차를 구하는 문제이기 때문에 큰 수와 작은 수의 순서를 위해 정렬을 해줬다.

정렬 후 for문을 돌리면서 두 수의 차가 가장 작은 숫자를 구해줬다.

ex) K = 4

1 3 5 9 100

 

case)

1 3 5 9 => 9 - 1 = 8

3 5 9 100 => 100 - 3 = 97

1 5 9 100 => 100 - 1 = 99

1 3 5 100 => 100 - 1 = 99

 

답은 8이다.

 

위의 예시처럼 숫자를 K개 단위로 끊은 후 그 중 가장 큰 값과 가장 작은 값을 빼주면 된다.

(근데 이 문제를 어제인가 그제인가 풀었는데 그냥 풀다 보니까 풀려서 이렇게 적어보니까 또 새롭다. 알고 맞힌 게 아닌 듯... ㅎ)

 

 

 

 

3. 코드 설명

 

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> arr, int K) {
    // 여기에 코드를 작성해주세요.
    int m = 20000, i;
    
    sort(arr.begin(), arr.end());
    
    for (i = 0; i <= arr.size() - K; i++)
        m = min(m, arr[K - 1 + i] - arr[i]);
    
    return m;
}

// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    vector<int> arr = {9, 11, 9, 6, 4, 19};
    int K = 4;
    int ret = solution(arr, K);

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret << " 입니다." << endl;
}

 

큰 수에서 작은 수를 빼주기 위해 미리 정렬해준다. 

그리고 K개로 나눠서 가장 큰 수와 작은 수를 빼주는 부분을 위와 같이 구현했다.

K - 1 + i번째 값에서 i번째 값을 빼주면 위의 예시처럼 값을 배열의 값을 돌아가며 배열을 쪼개는 효과를 낼 수 있다.

그 값들 중 가장 작았던 값을 변수 m에 저장하고 return 한다.

 

처음엔 쉬워 보여서 안 풀려서 짜증 났는데 지금 보니까 답을 생각해낸 게 용하네 ㅎ