[백준] 용액 (2467번)

난이도 : Gold5
Link : https://www.acmicpc.net/problem/2467
Tag : 구현, 이분탐색, 두 포인터
풀이일자 : 2024년 9월 24일

📌 문제 탐색하기

N : 용액의 개수
list : 용액 특성값 리스트

본 문제는 두 용액을 더해서 0과 가장 가까운 용액을 만드는 것이 목표이다.

가능한 시간복잡도

용액의 수인 N은 2 <= N <= 100,000 이며
각 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하이다.
최악의 시간복잡도에서 N = 100,000일때, 구할 수 있는 조합의 개수는 100,000 x 99,999이므로 시간복잡도상 문제가 발생할 수 있다.

따라서 본 문제는 투포인터 기법과 이분탐색을 통해 접근해야 한다.

📌 문제 접근 방법

투 포인터를 사용할 것으므로 두가지 포인터를 잡아야 한다.

여기서는 이미 정렬된 배열을 주기 때문에 start포인터는 가장 작은 용액 특성, end포인터는 가장 큰 용액 특성으로 잡고 시작한다.

그 다음 이분탐색을 이용하여 두 포인터의 위치를 변경해줄 예정이다.
이분탐색을 진행하면서 절대값중 가장 작은 값을 answer에 저장한다.

📌 코드 설계하기

1. n과 list를 입력받는다.
2. answerdp 초기값 abs(list[0]+list[-1])를 저장한다.
3. answer_index_start 포인터와 answer_index_end 포인터를 생성한다
4. 이분탐색에 사용될 start와 end를 설정한다.
5. 이분탐색을 진행한다.
   • tmp에 이분탐색하면서 answer와 비교할 용액을 저장한다.
   • 만약 절대값 tmp가 answer보다 작다면 answer를 abs(tmp)로 업데이트 한다.
   • answer_index_start와 answer_index_end를 start와 end로 업데이트 한다.
   • 만약 tmp < 0 라면 , start의 위치를 바꿔 이분탐색을 진행한다.
   • 만약 tmp > 0 라면, end의 위치를 바꿔 이분탐색을 진행한다.
   • 만약 tmp = 0 라면, 반복문을 종료한다.
6. 합친 용액 두개를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
list = list(map(int, input().split()))

answer = abs(list[0]+list[-1])
answer_index_start = 0
answer_index_end = n-1

start = 0
end = n-1
while start < end:
    tmp = list[start]+list[end]
    if abs(tmp) < answer:
        answer = abs(tmp)
        answer_index_start = start
        answer_index_end = end

    if tmp < 0 : #음수일 경우 시작점 index+1
        start = start + 1
    elif tmp > 0: #양수일 경우 끝점 index-1
        end = end - 1
    else: #0일 경우 종료
        break
print(list[answer_index_start], list[answer_index_end])