백준 2470 두 용액 파이썬 풀이

난이도 : 골드5

풀이일 : 2404221

https://www.acmicpc.net/problem/2470

2470번: 두 용액

---

문제 캡쳐

---

아이디어

• 용액을 정렬한다.
• 가장 왼쪽과 가장 오른쪽 용액을 초기 값으로 두고, 두 용액의 합을 저장된 값과 비교한다.
• 두 용액 합의 절댓값이 저장된 값보다 작으면, 저장된 값과 현재 인덱스를 저장한다.
• 두 용액의 합이 음수라면 front를 오른쪽으로 움직이고, 양수라면 rear를 왼쪽으로 움직인다.
• 반복문 종료 후 저장된 인덱스 용액을 출력한다.

---

전체 풀이코드

import sys

N = int(sys.stdin.readline())
fluid = list(map(int, sys.stdin.readline().split()))
fluid.sort()  # 용액 정렬

# 투포인터 알고리즘을 위한 초기 설정
front = 0
rear = N - 1
total = float('inf')

while front < rear:
    # 두 인덱스 용액의 합
    temp = fluid[front] + fluid[rear]
    # 저장된 절댓값보다 현재 용액의 합 절댓값이 작은 경우
    if abs(total) > abs(temp):
        total = temp
        # 인덱스 저장
        ridx, lidx = front, rear
    # 현재 용액의 합이 음수인 경우 front 이동
    elif temp < 0:
        front += 1
    # 현재 용액의 합이 양수인 경우 rear 이동
    else:
        rear -= 1

# 저장된 두 인덱스의 용액 출력
print(fluid[ridx], fluid[lidx])

---

상세 풀이코드

N = int(sys.stdin.readline())
fluid = list(map(int, sys.stdin.readline().split()))
fluid.sort()  # 용액 정렬

# 투포인터 알고리즘을 위한 초기 설정
front = 0
rear = N - 1
total = float('inf')

• fluid : 주어지는 용액 정보를 저장하는 배열로, 입력을 받은 후 정렬해준다.
• front : 왼쪽부터 출발할 포인터 인덱스를 의미한다.
• rear : 오른쪽부터 출발할 포인터 인덱스를 의미한다.
• total : 두 용액의 합을 저장할 변수로, 초기 아주 큰 수로 설정한 뒤 탐색을 시작하였다.

 

while front < rear:
    # 두 인덱스 용액의 합
    temp = fluid[front] + fluid[rear]
    # 저장된 절댓값보다 현재 용액의 합 절댓값이 작은 경우
    if abs(total) > abs(temp):
        total = temp
        # 인덱스 저장
        ridx, lidx = front, rear
    # 현재 용액의 합이 음수인 경우 front 이동
    elif temp < 0:
        front += 1
    # 현재 용액의 합이 양수인 경우 rear 이동
    else:
        rear -= 1

# 저장된 두 인덱스의 용액 출력
print(fluid[ridx], fluid[lidx])

• while 반복문 : front가 rear 보다 작은 경우에 반복을 수행한다.
• temp : 투 포인터의 현재 위치인 front, rear가 가리키고 있는 두 용액의 합을 저장하는 변수이다.
• if abs(total) > abs(temp) : 만약, 현재 저장된 total의 절댓값이 방금 구한 두 용액의 합 temp의 절댓값보다 크다면, total, ridx, lidx를 재할당한다.
• ridx, lidx : 최종 결과 출력을 위해 두 용액 합의 절댓값이 가장 작은 인덱스 정보를 저장한다.
• elif temp < 0 : 절댓값을 0 가까이 만드는 것이 목적이므로, 현재 용액의 합이 음수라면, front를 한 칸 오른쪽으로 이동시킨다.
• else : 만약 현재 용액의 합이 양수라면, rear를 한 칸 왼쪽으로 이동시킨다.
• 최종적으로 저장되어 있는 두 인덱스가 가리키는 용액들을 출력한다.

---

느낀점

• 언젠가 엄청 비슷한 문제를 풀었어서 풀이가 어렵지 않았다. 며칠 계속 집을 떠나 있는 바람에 쉬었으니 적응하는 쉬운 문제를 풀었다고 생각해야지.
• 다만, 투 포인터 자체가 익숙하지 않아서 조금 더 익숙해질 수 있도록 다른 문제들을 풀어봐야 할까 싶다.