투 포인터

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 세 용액의 합이 0과 가장 근사한 값을 찾아야 한다. 용액의 수가 5000 이하이기 때문에 최악일 경우 5000 * 2500 = 7500000의 연산을 계산하기 때문에 시간 복잡도에 대한 걱정 없이 해결할 수 있었다. 기준점 i번째의 값부터 n-1의 값까지 j번째와 k번째의 합들 중에서 최솟값을 구했다. 여기서 j번째는 i+1, k번째는 n-1번째로 설정하여 투 포인터 알고리즘으로 해결하였다. i, j, k번째의 합이 비교대상 comp과 비..
풀이 과정 해당 문제는 단순한 투 포인터 문제이다. 두 값의 합이 0과 가까운 쌍을 찾으면 끝이다. 1. 주어진 x 배열을 정렬시킨다. 2. 문제에서 수들의 합이 매우 크기 때문에 minV를 매우 큰 값으로 설정하였다. 3. 투 포인터를 사용하기 때문에 0번째 인덱스와 n-1 인덱스부터 시작한다. 4. 오른쪽 인덱스 s와 왼쪽 인덱스 e의 합을 m으로 지정한다. 5. 절댓값 m이 minV보다 작을 경우 minV를 m으로 업데이트해준다. ans를 현재 x [s], x [e]로 업데이트해준다. 6. minV이 0이면 반복문을 종료하고 현재 ans을 출력한다. 7. m 값이 0보다 작을 경우 오른쪽 인덱스를 증가시키고 반대일 경우 왼쪽 인덱스를 감소시킨다. 풀이 코드 n,*x= map(int,open(0).r..
행복한쿼콰
'투 포인터' 태그의 글 목록