[C++] 백준 2230 : 수 고르기

문제

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

 

 

풀이

이 문제에서는 배열의 크기가 최대 10,000 이기 때문에 이중 for문을 이용하여 O(N^2)의 복잡도로 구현하면 시간 초과가 날 수 있다. 따라서 투포인터를 이용하여 구현한다.

1. 오름차순(내림차순도 상관 없음)으로 입력 배열 정렬, ans(=최솟값) INF 로 초기화
2. start = 0, end = 0
3. arr[end] - arr[start] < M : end++
4. arr[end] - arr[start] >= M : start++, ans 갱신
5. 최종 ans 출력

위의 과정을 코드로 구현하면 된다.

 

그런데 사실 완전탐색에 가깝게 구현해도 통과가 되긴 한다. 뭔가 테스트케이스가 섬세하지 못하게..? 짜여있는 것 같기도 하다. (통과 안 할 줄 알고 이중 for문으로 구현한 코드를 돌렸는데 통과된다.)

 

 

코드 - 투포인터

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, ans = 2000000000;
int arr[100001];

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    // 오름차순 정렬 
    sort(arr, arr+n);

    int start = 0, end = 0;
    while(end < n){
    	
        // 차이 계산 
        int d = arr[end] -arr[start];
        
        // 차이가 M 이상인 경우,
        if(d >= m){
        
        	// 현재의 차이가 최솟값인 경우, 최솟값(ans) 갱신
            if(d <ans){
                ans = d;
            } 
            
            // start 증가
            start++;
        }
        
        // 차이가 M보다 작은 경우, end 증가(차이를 늘려야 함)
        else{
            end++;
        }
    }

    cout << ans << "\n";

    return 0;
}

 

 

코드 - 이중 for 문 이용

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, ans = 2000000000;
int arr[100001];

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    // 오름차순 정렬 
    sort(arr, arr+n);
    for(int i=n-1; i>=1; i--){
        for(int j= i-1; j>=0; j--){
            int d = arr[i] - arr[j];
            if(d >=m){
                if(d < ans) {
                    ans = d;
                }
                break;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

 

 

추가로, 각각 돌렸을 때 결과는 다음과 같다. 아래가 이중 for문, 위가 투포인터 이용한 코드의 결과이다. (시간 차이~)