BOJ 2230 : 수 고르기

·2023년 1월 29일
0

알고리즘 문제 풀이

목록 보기
47/165
post-thumbnail

문제

풀이 요약

투 포인터를 활용한 문제.

풀이 상세

  1. 투 포인터 stst, eded 을 지정하여 시작한다. 첫 시작은 모두 idx=0idx = 0 에서 부터 시작한다.

  2. 정확한 탐색을 위해 먼저 오름차순으로 정렬한 후 탐색을 시작한다

    • diffdiff 의 값이 현재 MM 값 보다 작다면, 더 큰 값을 보기 위해, eded 를 늘린다.

    • diffdiff 의 값이 현재 MM 값 보다 크다면, 이후 eded 의 오른쪽 부분은 모두 큰 값이 나올테니, stst 를 늘려, eded 부분을 다시 탐색한다.

  3. 탐색과정을 통해 찾아낸 최소 차이 값을 출력한다.

배운 점

  • 여러 태케를 구상하여, mid 값 설정을 통한 이분탐색을 시도하려 했으나 원하는대로 구현이 되지 않았다.

  • 설마 그냥 1씩 증가시키는게 될까… 했는데 되었다. 고민하다가 생각이 안나면 그냥 일단 시도해보자.

  • ios::sync_with_stdio(0) , cin.tie(0) 은 쓰고 시작하자. 속도가 많이 차이난다.

  • #include <bits/stdc++.h> 이제 안써야겠다! 편해서 좋은데 코테 안되는 곳도 있다 하고, c++ 이랑 좀 처럼 안 친해진다.

정답

#include <algorithm>
#include <iostream>
#define MAX 2000000001
using namespace std;
int N, M, st, ed;
int arr[100000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    sort(arr, arr + N);
    int res = MAX;
    while (st < N && ed < N && st <= ed) {
        int diff = arr[ed] - arr[st];
        if (diff < M)
            ed++;
        else {
            res = min(res, diff);
            st++;
        }
    }
    cout << res;
}
profile
새로운 것에 관심이 많고, 프로젝트 설계 및 최적화를 좋아합니다.

0개의 댓글