끄적끄적
백준 [2230] 수 고르기 - 투포인터 본문
출처 : https://www.acmicpc.net/problem/2230
수 고르기
2 초 | 128 MB | 4654 | 1460 | 1041 | 28.781% |
문제
N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.
입력
첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다.
출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
예제 입력 1
3 3
1
5
3
예제 출력 1
4
알고리즘 분류
알고리즘 분류에 보면 정렬과 두 포인터라고 되어 있는데.. 돌고 돌아 풀었다.
처음에는 전체 경우의 수를 다 찾아보는 방식으로 풀었는데, 그렇게 하니 약 O(N^2)이 나와 시간 초과에 걸렸다.
그래서 정렬을 한 뒤 while문을 돌려주면 된다.
(만약 정렬을 하지 않고 밑의 while문만 돌린다면 틀린다. 이유는 while문 안 조건의 기준이 index가 아니라 M이기 때문
범위를 벗어나는 경우와 같은 예외가 발생하기 때문인 것 같다.)
정렬을 했기 때문에 차이가 M보다 작다면 차이를 늘려야 하므로, ptr2를 하나 증가 시켜준다.
또한 M과 같다면 조건을 만족하면서 최소 차이이므로 바로 while문을 탈출시켜주면 되고,
나머지는 M보다 큰 경우이므로(정렬을 했기 때문에 뒤는 볼 필요가 없다), 그 때는 ptr1을 증가시켜주면 된다.
따라서 시간복잡도는 정렬 O(NlogN), 투포인터 탐색 O(N) 따라서 총 O(NlogN)이다.
*참고로 int 입력 범위는 약 20억이므로, 다 int로 선언해주면 된다.
'코테준비' 카테고리의 다른 글
백준[15486] 퇴사2 - dp (0) | 2021.08.05 |
---|---|
백준 [2470] 두 용액 - 투포인터 (0) | 2021.07.16 |
백준 [7795] 먹을 것인가 먹힐 것인가 (이분탐색) (0) | 2021.07.14 |
백준 [11728] 배열 합치기 - 투포인터 (0) | 2021.07.14 |
백준 [2003] 수들의 합 2 - 투포인터 (0) | 2021.07.14 |