[백준] 2470번 두 용액 파이썬 풀이

---

2470번: 두 용액

---

[문제]

---

[코드]

import sys
input = sys.stdin.readline

N = int(input())
solution = sorted(list(map(int, input().split())))

##투포인터
start = 0
end = N-1

target = abs(solution[0] + solution[-1])#절대값 -> 0까지 거리
result = [solution[0], solution[-1]] #초기값 설정

while start < end:
    l = solution[start]
    r = solution[end]

    d = l + r
    zero_d = abs(d)

    if zero_d < target: #현재 가장 가까운 거리보다 작다면
        target = zero_d
        result = [l, r]

    if d < 0: #현재 합이 0보다 작다면 start를 1칸 올려 합을 올려
        start += 1
    else: #반대면 end를 한칸내려서 합을 낮춰
        end -= 1

print(*result)

---

[해설]

투 포인터 문제는 처음이었기 때문에

기존 이분탐색으로 접근을 하다가 많은 시간을 소모하였다

결국 아래의 풀이를 참고하고 이해를 할 수 있었다

[알고리즘] 두 용액 백준 2470 python

 

문제의 핵심

1. 투포인터를 이용한 풀이

2. 그리고 두 값의 합이 0보다 클때와 작을때를 어떻게 활용해서 start, end지점을 조절해줄지

 

import sys
input = sys.stdin.readline

N = int(input())
solution = sorted(list(map(int, input().split())))

##투포인터
start = 0
end = N-1

target = abs(solution[0] + solution[-1])#절대값 -> 0까지 거리
result = [solution[0], solution[-1]] #초기값 설정

코드 풀이는 생각보다 간단하다

1. 우선 값의 갯수를 N으로 받아 변수로 저장한다

2. 그리고 용액의 각 값을 list로 받아서 정렬한다 

 

그런다음 투포인터를 지정해주는데

start는 현재 용액 배열의 첫번째 인덱스 0

end는 N-1을 하여 마지막 인덱스를 지정해준다

---

그리고 target은 현재 선택된 값 2개의 합을 구해서 절대값을 취하는데 

이것이 의미하는 것은 현재 합성 용액의 값과 0사이의 거리를 의미한다  - 절대갑의 의미를 활용

 

그리고 최종적으로 출력할 합성에 활용된 용액의 값을 리스트로 묶어서 result라는 변수에 지정해두는데

이는 추후 while문에서 target와 result를 갱신하면서

0부터 합성 용액까지의 거리가 최소인 상황을 target과 result에 저장할 것이기 때문에 만들어 주는 것이다

 

---

 

while start < end:
    l = solution[start]
    r = solution[end]

    d = l + r
    zero_d = abs(d)

    if zero_d < target: #현재 가장 가까운 거리보다 작다면
        target = zero_d
        result = [l, r]

    if d < 0: #현재 합이 0보다 작다면 start를 1칸 올려 합을 올려
        start += 1
    else: #반대면 end를 한칸내려서 합을 낮춰
        end -= 1

그리고 start 보다 end 인덱스가 클동안 while문을 돌아주는데

먼저 현재 start의 값과 end의 값을 합쳐서 합성용액의 값 d를 구해주고

이 d를 절대값 취한 0까지의 거리인 zero_d를 구해준다

---

 

그리고 만약 zero_d가 - 그러니까 0까지의 거리가, 기존 0까지의 거리보다 작다면

target을 현재 zero_d로 지정해주고 

result를 현재의 start 값과 end 값으로 지정해준다

그렇지 않다면 pass

---

그리고 앞에서 구한 d - 합성용액의 값이 0 보다 작다면 start의 인덱스를 1올려서 다음 합성용액의 값을 키워주고

만약 d가 0보다 작다면 end의 인덱스를 1줄여서 다음 합성 용액의 값을 줄여준다

 

이부분을 이해하는데 조금 오래 걸렸다 자세히 살펴보자

 

예시를 문제의 예제로 설명하면 다음과 같다

-2 4 -99 -1 98
#정렬
-99 -2 -1 4 98

값들이 인풋으로 주워지고 이를 정렬하면 다음과 같다

 

여기서 초기 d는 -99 + 98로 -1임으로 start 인덱스가 1증가한다

 

만약 합이 음수인 상황에서 end를 줄이면  더 작은 음수가 나옴으로 

절대값을 취했을 때 기존 target보다 작을 경우가 존재하지 않는다

따라서 합이 음수일 때는 start 인덱스을 올려서 더 높은 합을 만든다음

이를 절대값 취해서 현재의 target과 비교하는 경우만 존재하면 된다

 

반대로 합이 양수인 상황에서 start를 증가 시키면 더 큰 양수가 나오기 때문에

절대값을 취했을 때 기존의 target보다 작을 경우가 존재하지 않는다

따라서 합이 양수일 경우에는 end를 줄여서 더 작은 양수를 만들어

이를 절대값 취해 - 사실 취할 필요없다, target과 비교하는 경우만 존재하면 된다

 

이를 시각적으로 나타내면 다음과 같다

loop / value	-99	-2	-1	4	98
loop 1	s				e
loop 2		s			e
loop 3		s		e
loop 4		s	e
loop 5			s,e

 즉, 기존 이중 for문을 활용해서 모든 경우의 수를 판단했을 때 - 완전탐색으로 보았을 때

 O(N^2)인데 

 

 

위의 투포인터를 활용하면

O(N)이 된다