반응형
https://www.acmicpc.net/problem/2470
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00
www.acmicpc.net
소스코드
풀이
★ 정렬된 리스트 a의 시작부분과 끝부분을 투포인터로 잡고, 그 값들을 더한 값이 0에 가까운 수들을 찾아줍니다.
lt가 rt보다 작을 때만 반복문을 도는 이유는 문제에서 n개의 용액들 전부 특성이 다르기에 중복되는 수가 없기 때문입니다.
★ 투포인터를 더한 절대값(mid값)이 ans보다 작으면 그 값이 0에 가장 가까운 값이 됩니다. 만약 mid 값이 0이 되면 바로 칮은 것이기에 반복문을 빠져나가고 값이 양수일 경우 mid값보다 큰 수들은 무조건 0에서 더 멀기 때문에 rt를 -1 해줍니다. 반대로 mid값이 음수가 나오는 경우 mid값보다 작은 값들은 전부 0에서 멀기 때문에 lt를 +1 해줍니다 !
★ 반복문을 돌면서 0에 가장 가까운 두 수를 찾아준 뒤 그 수를 오름차순 정렬하여 출력합니다
배운점
- 원소들 사이에 중복되는 값이 없는 경우, lt가 rt보다 작을 때까지만 반복문을 수행하면 된다. (보통 이분탐색 문제는 lt <= rt 까지 반복을 수행함)
- 이분탐색 문제라고 해서 무조건 mid값을 구해서 문제를 해결하는 것은 아니구나 ~~
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1072번: 게임 (Python) (0) | 2023.06.06 |
|---|---|
| [백준 알고리즘] 17299번: 오등큰수 (Python) (0) | 2023.06.06 |
| [백준 알고리즘] 10815번: 숫자카드 (Python) (0) | 2023.06.05 |
| [백준 알고리즘] 1920번: 수 찾기 (Python) (0) | 2023.06.05 |
| [백준 알고리즘] 2812번: 크게 만들기 (Python) (0) | 2023.06.03 |