[Algorithm] Baekjoon 2230번 : 수 고르기

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

int minNum = 2000000002;
int arr[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
    vector<int> v;
    
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        int temp = 0;
        cin >> temp;
        v.push_back(temp);
    }
 
    sort(v.begin(), v.end());
 
    int left = 0;
    int right = 0;
 
    while (right < n)
    {
        int gap = v[right] - v[left];
 
        if (gap == m)
        {
            cout << gap;
            return 0;
        }
 
        if (gap >= m)
        {
            minNum = min(minNum, v[right] - v[left]);
 
            ++left;
        }
        else
        {
            ++right;
        }
    }
 
    cout << minNum;
}

여러유형을 풀어보는것도 중요해서 오랜만에 투포인터 문제를 풀어봤다.

그닥 어려운 문제는 아닌데, m이상의 차이가 나는 두 수를 선택했을 때, 최소값을 출력하는 문제다.

수의 차이를 이용해야하는 문제라서 일단 입력받은 값들을 한번 정렬해준다.

그래야 투포인터개념이 적용될 수 있다. 즉, left와 right를 이동하는데 의미가 생긴다.

 

같은값을 두번 사용할 수 있다고 하니 left, right 둘 다 0부터 시작한다.

그리고 두 값의 차이가 m이상일 경우 minNum을 업데이트 한다음 다시 간격을 좁혀야하니 left값을 1 증가시키고, 두 값의 차이가 m 미만이라면 m이상이 되게 해야하기 때문에 right를 1 증가시킨다.

 

해당 과정을 반복하다 right가 범위를 벗어나면 종료시킨다.