문제
입력 출력 예시
문제 요약
- 서로 다른 두 용액을 선택해서 특성값의 합이 0에 가장 가까운 두 용액을 찾기.
- 각 용액의 특성값은 -10억 ~ 10억.
- N은 최대 100,000개.
- 1초 안에 해결해야 함.
| 요구조건 |
의미 |
| 서로 다른 두 개의 용액을 고른다 |
같은 용액 두 번 고르면 안 된다 |
| 합이 0에 가까워야 한다 |
합의 절댓값이 최소여야 한다 |
| N은 최대 100,000이고 시간 제한이 1초 |
O(N²) 불가능 → O(N log N) 이하 필요 |
해결 전략: 투 포인터 알고리즘
1. 용액의 특성값 정렬
"정렬" 해야 숫자의 크기에 따라 탐색 방향을 정할 수 있다.
- 오름차순으로 정렬하면, 작은 값(left 포인터의 값)과 큰 값(right 포인터의 값)을 이용해서 둘의 합이 양수인지 음수인지에 따라 방향을 조정할 수 있다.
정렬하지 않으면, 두 값을 보고 "왼쪽으로 갈까? 오른쪽으로 갈까?"를 결정할 수 없다.
=> O(N log N) 정렬은 필수.