728x90
문제 (링크)
https://www.acmicpc.net/problem/2467
나의 풀이
이 문제는 투포인터와 이진탐색을 모두 사용할 수 있다.
1) 투포인터 사용
import sys
input = sys.stdin.readline
n = int(input())
liquids = list(map(int, input().split()))
left_idx = 0
right_idx = n - 1
ans = abs(liquids[left_idx] + liquids[right_idx])
ans_left = left_idx
ans_right = right_idx
while left_idx < right_idx: # left_idx와 right_idx는 만나면 안된다
tmp = liquids[left_idx] + liquids[right_idx]
if abs(tmp) < ans:
ans_left = left_idx
ans_right = right_idx
ans = abs(tmp)
if ans == 0:
break
if tmp < 0:
left_idx += 1
else:
right_idx -= 1
print(liquids[ans_left], liquids[ans_right])
코드 설명 및 풀이법
투포인터 알고리즘을 사용하기 위해서 생각해야할 것은 딱 두가지이다.
두 개의 포인터를 각각 무엇으로 잡을지와, 각 포인터가 움직여야할 상황을 정의하는 것이다.
테스트케이스에서 확인할 수 있듯이 용액 중 특성값이 가장 작은 값과 큰 값을 더하는 것이 0에 가까운 특성값을 만드는 하나의 방법처럼 보인다.
따라서, 특성값이 가장 작은 0번 인덱스 값과 특성값이 가장 큰 마지막 값을 초기 포인터로 설정해주었다.
이후, 두 포인터가 가르키는 값을 더한 후 해당 값의 절대값이 0과 가장 가까운 것을 각각 저장해준다.
포인터를 이동시킬때는 두 포인터가 가르키는 값을 더한 값이 0보다 크냐 작냐를 기준으로 한다.
만약 해당 값이 0보다 작다는 것은 두 포인터가 더한 값을 증가시켜줘야하기 때문에 왼쪽 포인터를 1 더해주었고, 그게 아니라면 값을 감소시켜줘야하기 때문에 오른쪽 포인터에서 1을 빼주었다.
2) 이진탐색
import sys
input = sys.stdin.readline
n = int(input())
liquids = list(map(int, input().split()))
ans = float("INF")
ans_left = 0
ans_right = 0
for i in range(n-1):
current = liquids[i]
start = i + 1
end = n - 1
while start <= end:
mid = (start + end) // 2
tmp = current + liquids[mid]
if abs(tmp) < ans:
ans = abs(tmp)
ans_left = i
ans_right = mid
if tmp == 0:
break
if tmp < 0:
start = mid + 1
else:
end = mid - 1
print(liquids[ans_left], liquids[ans_right])
코드 설명 및 풀이법
용액의 i번째 값과 i+1 ~ n까지의 값의 합을 각각 이진탐색으로 구해서 0과 가장 가까운 쌍을 찾는 방식이다.
start와 end를 증감시키는 로직은 투포인터와 크게 다르지 않다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 1208번 부분수열의 합 2 - 파이썬(Python) (0) | 2021.09.30 |
---|---|
[백준] 12865번 평범한 배낭 - 파이썬(Python) (0) | 2021.09.29 |
[백준] 1107번 리모컨 - 파이썬(Python) (0) | 2021.09.27 |
[백준] 1182번 부분수열의 합 - 파이썬(Python) (1) | 2021.09.26 |
[백준] 2110번 공유기 설치 - 파이썬(Python) (0) | 2021.09.23 |