세 용액
면접 대비시간 제한1초메모리 제한256 MB
최대 5000개의 서로 다른 정수 중 세 개를 골라 합이 0에 가장 가깝게 만드는 조합을 정렬과 투 포인터로 찾는 문제입니다.
문제
한 과학 연구소에는 여러 종류의 산성 용액과 알칼리성 용액이 있다. 각 용액에는 그 특성을 나타내는 정수 하나가 붙어 있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 표현한다.
서로 다른 세 용액을 같은 양으로 섞으면, 혼합 용액의 특성값은 선택한 세 용액의 특성값을 모두 더한 값이다. 연구소는 주어진 용액 중 서로 다른 세 용액을 골라, 혼합 용액의 특성값이 0에 가장 가까워지게 하려고 한다.
주어진 특성값이 [-2, 6, -97, -6, 98]이라면 -97, -2, 98을 섞어 특성값이 -1인 용액을 만들 수 있고, 이 값이 0에 가장 가깝다. 최적의 세 용액이 모두 산성일 수도 있고, 모두 알칼리성일 수도 있다.
주어진 용액들 중에서 특성값의 합이 0에 가장 가까워지는 서로 다른 세 용액의 특성값을 구하시오.
입력
첫째 줄에 전체 용액의 수 N이 주어진다. N은 3 이상 5,000 이하의 정수이다.
둘째 줄에는 각 용액의 특성값을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 각 값은 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 특성값은 모두 서로 다르다. 입력이 산성 용액만으로 이루어질 수도 있고, 알칼리성 용액만으로 이루어질 수도 있다.
출력
특성값의 합이 0에 가장 가까워지는 세 용액의 특성값을 오름차순으로 출력한다.
조건을 만족하는 세 용액의 조합이 여러 개라면 그중 아무것이나 하나를 출력한다.