백준 2470번 두 용액

많은 종류의 산성 용액과 알칼리성 용액이 있을 때, 어떠한 두 용액을 섞었을 경우 두 용액의 특성값의 합이 0에 가장 가까운 용액을 구하는 문제입니다.

(산성 용액의 특성값은 1~1,000,000,000까지의 양의 정수이고, 알칼리성 용액의 특성값은 -1 ~ -1,000,000,000까지의 음의 정수입니다.)

 

시도 1.

용액의 오름차순으로 정렬하고, 특성값의 합이 0에 가장 가까운 두 용액을 찾기 위한 방법을 고민했습니다.

입력 설명에 모든 용액이 산성 용액 혹은 알칼리성 용액으로만 주어지는 경우가 있다고 하여, 0에 가장 가까운 숫자를 찾는 것에 집중했습니다.

 

아래는 제가 생각한 예시였습니다.

-101 -90 -5 10 12 110

위와 같이 용액이 주어졌을 경우 제 생각에는 0에 가까울수록 다른 특성의 두 용액의 합 또한 작아질 것이라고 생각했습니다.

이 경우의 답은 -5 10 이 될 것입니다.

그러므로 우선 이분탐색으로 0에 가까운 수를 찾고 해당 주변의 숫자들의 합 중 가장 작은 것을 출력하면 될 것이라고 생각했습니다.

 

하지만, 음수와 양수 용액이 적절한 비율로 나오는 아래와 같은 예시일 때가 예외가 되었습니다.

-101 -90 -5 10 12 104

이번 예시의 경우 0에서 가장 멀리 있는 두 용액 -101과 104가 정답이 됩니다.

 

그러므로 다른 방법을 생각해보았습니다.

 

시도 2.

정렬과 이분탐색을 이용하려는 것은 그대로 가져갔습니다.

이번에는 각 특성값을 양수는 음수로, 음수는 양수로 뒤집었을 때, 가장 가까운 특성값을 가진 용액을 찾아 각 용액마다 특성값의 합이 0에 가장 가까운 용액을 찾도록 해보려고 했습니다.

 

-101 -90 -5 10 12 104

이와 같은 예시가 있을 경우를 생각해보겠습니다.

-101을 뒤집었을 때 101이 되고 101과 가장 가까운 양수의 용액은 104가 됩니다. 그러므로 -101과 특성값의 합이 0에 가장 가까운 용액은 104가 됩니다. 그리고 그 합은 3이 됩니다.

-90을 뒤집었을 때 90이 되고 90과 가장 가까운 양수의 용액은 104가 됩니다. 그러므로 -90과 특성값의 합이 0에 가장 가까운 용액은 104가 됩니다. 그리고 그 합은 14가 됩니다.

...

이런식으로 모든 용액의 특성값의 합이 0에 가장 가까운 용액을 찾은 뒤 그 합이 가장 작은 두 용액을 출력해보려고 했습니다.

 

하지만, 이분탐색으로 뒤집은 수와 가장 가까운 수를 찾는 로직과 양수만 주어졌을 경우, 음수만 주어졌을 경우를 생각했을 때 깔끔하게 떨어지지 않아 시도를 이어나가기 어려웠습니다. 또한, 시간 복잡도에서 모든 숫자를 탐색해야했고 이분탐색으로 가장 가까운 수를 찾는데에 N*logN 이 걸리기 때문에 시간 초과가 나올 것으로 예상되어 더 이상 진행하지 않았습니다.

 

시도 3.

모든 용액은 특성값의 합이 0에 가장 가까운 용액은 정해져 있다고 생각했습니다. 그러므로 모든 용액을 한 번씩만 탐색하면서 해당 용액을 찾을 수 있도록 투 포인터를 도입했습니다.

s,e=0,len(fluid)-1

두 개의 포인터를 정하고 시작점인 s는 0, 끝 점인 e는 주어진 용액의 길이-1 로 정했습니다.

 

이 후, 해당 포인터가 가리키는 용액의 특성값을 더하고, 해당 특성값 합의 절대값이 현재까지의 특성값 최소값보다 작다면 현재까지의 최소값을 현재 용액의 특성값 합의 절대값으로 교체해줄 수 있도록 했습니다.

minValue = 2_000_000_000

while :
    composite=fluid[s]+fluid[e]
    
    if minValue>abs(composite):
        minValue=abs(composite)
        answer=[fluid[s],fluid[e]]

그 다음,  특성 값의 합이 0보다 작다면 현재 두 포인터 중 s가 가리키는 용액의 특성값의 절대값이 더 크다는 말이므로 s를 1 증가시켜줍니다. 특성 값의 합이 0보다 크다면 현재 두 포인터 중 e가 가리키는 용액의 특성값의 절대값이 더 크다는 말이므로 e를 1 감소시켜줍니다.

특성 값의 합이 0이라면 해당 두 용액의 특성값의 합이 가장 0에 가까운 용액이므로 반복문을 빠져 나옵니다.

이를 s가 e보다 작을 때까지만 반복해줍니다.

minValue = 2_000_000_000
answer=[]
s,e=0,len(fluid)-1
while s<e:
    composite=fluid[s]+fluid[e]
    
    if minValue>abs(composite):
        minValue=abs(composite)
        answer=[fluid[s],fluid[e]]
    
    if composite<0:
        s+=1
    elif composite>0:
        e-=1
    else:
        break

print(answer[0],answer[1])

 

 

 

 

해결

이번 문제는 두 번째 시도까지 스스로 시도해보다가 백준 문제 아래쪽의 알고리즘 분류를 보고 해결했던 문제입니다. 스스로 풀지 못했다는 아쉬움이 있습니다... 그래도 이번 문제를 통해 투 포인터를 적용하면 좋을 것 같은 문제를 알아볼 수 있는 선구안을 길렀다고 생각하고 복습해보아야 될 것 같습니다.

알고리즘 문제를 연습한다는 것은 문제를 보고 어떤 알고리즘을 적용해야 겠다는 선구안을 기르는 것이라고 생각하기 때문에 최대한 다양한 문제를 연습해보는 것이 좋겠다는 생각이 들었습니다.

 

문제 링크 : https://www.acmicpc.net/problem/2470

2470번: 두 용액