[백준] 2470번: 두 용액

🔈 문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 

📝입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

 

📑출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

📚 문제 풀이

문제를 읽고 처음에는 어떻게 접근해야 잘 접근했다고 소문이 날까 고민하다가, 투 포인터로 접근하기로 했다.

투포인터 알고리즘 문제를 아직 많이 풀어보지는 못해서, 차근차근 고민해가며 코드를 작성했다.

 

앞쪽에는 산성용액, 뒷쪽에는 알카리성용액이 위치하도록 정렬을 해준다.

용액 a와 용액 b를 더하여 0과 제일 가까운 a,b를 찾을 것인데, a는 첫번째 인덱스부터, b는 마지막 인덱스부터 시작한다.

a+b < 0 일때는 더한 값을 조금더 올려주기 위해 a의 인덱스를 하나 올린다. 

a+b > 0 일때는 더한 값을 내려주기 위해 b의 인덱스를 하나 낮춘다.

이러면 O(N)의 시간복잡도로 문제 해결이 가능하다.

 

💻 코드

n=int(input())
nums=sorted(list(map(int,input().split())))
f_idx, b_idx=0,n-1
ans=[] # 후보군 담을 배열

while f_idx<b_idx: # 종료조건은 a가 b를 넘어가지 않게
    solution=nums[f_idx]+nums[b_idx] # 두 용액을 더함
    ans.append([abs(solution),nums[f_idx],nums[b_idx]]) # 후보 배열에 삽입
    if solution<0: # 0보다 작다면 값을 키워주기 위해 a의 인덱스 올림
        f_idx+=1
    elif solution>0: # 0보다 크다면 값을 줄이기 위해 b인덱스를 내림
        b_idx-=1
    else: # 0이라면 아묻따 프린트 후 종료
        print(nums[f_idx], nums[b_idx])
        exit()
ans.sort() # 후보 정렬
print(ans[0][1],ans[0][2])

 

🍭 시행착오

위에 작성되어 있는 코드로 했더니 308ms 가 나왔다. 다른 분들의 코드를 보니 후보군을 배열에 삽입한 것이 아니라 그때그때 비교해가며 정답을 갱신하였다.

그렇게 변경하니 시간이 절반정도 줄었다.

 

if ans[0]>abs(solution):
        ans[0]=abs(solution)
        ans[1]=nums[f_idx]
        ans[2]=nums[b_idx]

 

 

🔗 문제링크 두 용액

2470번: 두 용액

그림/ 정서용