서론
오늘의 코딩 테스트 문제는 '수 고르기'다. 백준 2230번. 투 포인터 알고리즘을 사용해 해결했다.
문제 요약
•
N개의 정수로 이루어진 수열에서 두 수를 고른다.
•
두 수의 차이가 M 이상이면서 가장 작은 경우를 찾는다.
•
1 ≤ N ≤ 100,000
•
0 ≤ M ≤ 2,000,000,000
•
0 ≤ |A[i]| ≤ 1,000,000,000
접근 방식
1.
수열을 오름차순으로 정렬한다.
2.
투 포인터 알고리즘을 사용한다.
•
왼쪽 포인터를 기준으로 오른쪽 포인터를 이동시킨다.
•
차이가 M 이상이 되면 결과를 갱신하고 왼쪽 포인터를 이동한다.
3.
최소 차이를 찾을 때까지 반복한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
vector<int> A(N);
for (int i = 0; i < N; i++)
cin >> A[i];
sort(A.begin(), A.end());
pair<int, int> answer = {*(A.begin()), *(A.end()-1)};
int l = 0, r = 0;
while (l < N)
{
while (((r + 1) < N) && ((A[r] - A[l]) < M))
{
r++;
}
if ((A[r]-A[l]) >= M && (answer.second-answer.first) > (A[r]-A[l]))
{
answer = {A[l], A[r]};
}
if (A[l]-A[r]==M)
break;
l++;
}
cout << answer.second - answer.first << endl;
return 0;
}
C++
복사
구현 과정
1.
입력 받은 수열을 정렬했다.
2.
두 개의 포인터(l, r)를 초기화했다.
3.
왼쪽 포인터가 끝에 도달할 때까지 반복했다:
•
오른쪽 포인터를 이동시키며 차이가 M 이상이 되는 지점을 찾았다.
•
조건을 만족하면 결과를 갱신했다.
•
차이가 정확히 M이면 즉시 종료했다.
4.
최종 결과를 출력했다.
회고
1.
투 포인터 알고리즘을 사용해 O(N)의 시간 복잡도로 해결할 수 있었다.
2.
뭐 정렬에 O(N log N)이 소요되는 거 같지만, 전체적으로는 효율적인 해결책이다.
3.
Copilot이 켜져 있어서 그냥 풀었는데, 덕분에 변수 잘 못 쓰고 한참 헤매었다.
4.
투 포인터 알고리즘 관련 문제를 더 풀어볼 예정이다.
