[Gold V] 용액 - 2467
성능 요약
메모리: 125416 KB, 시간: 116 ms
분류
이분 탐색, 두 포인터
제출 일자
2024년 8월 25일 07:02:20
문제 설명
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.
입력
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
풀이
# 1. 데이터 입력 받기
N = int(input())
arr = list(map(int, input().split()))
# 2. 투 포인터 준비
left, right = 0, N - 1 # 양 극단
# sol_left, sol_right : 최소값을 만드는 두 수의 인덱스
sol_left = left
sol_right = right
# solution : 현재까지 발견한 두 수의 합의 절대값 중 최소값
solution = abs(arr[left] + arr[right])
# 3. 투 포인터 알고리즘
while left < right :
tmp = arr[left] + arr[right] # 지금 섞은 용액의 pH 비교
if abs(tmp) < solution : # tmp의 절대값이 solution보다 작을 경우
sol_left = left # sol_left 갱신
sol_right = right # sol_right 갱신
solution = abs(tmp) # solution 갱신
if tmp == 0 : # tmp 가 0이면 정답이므로 즉시 루프 중단
break
if tmp < 0 : # tmp < 0 이라면
left += 1 # left 를 오른쪽으로 한 칸 이동
else : # tmp > 0 이라면
right -= 1 # right 를 왼쪽으로 한 칸 이동
print(arr[sol_left], arr[sol_right])1. 입력 및 초기화
# 1. 데이터 입력 받기
N = int(input())
arr = list(map(int, input().split()))# 2. 투 포인터 준비
left, right = 0, N - 1 # 양 극단left : 리스트의 시작 인덱스
right : 리스트의 끝 인덱스
# sol_left, sol_right : 최소값을 만드는 두 수의 인덱스
sol_left = left
sol_right = right
# solution : 현재까지 발견한 두 수의 합의 절대값 중 최소값
solution = abs(arr[left] + arr[right])sol_left, sol_right : 최소값을 만드는 두 수의 인덱스
solution : 현재까지 발견한 두 수의 합의 절대값 중 최소값
2. 투 포인터 알고리즘
# 3. 투 포인터 알고리즘
while left < right :
tmp = arr[left] + arr[right] # 지금 섞은 용액의 pH 비교두 포인터(left, right)를 사용해 리스트를 탐색, left는 0에서, right는 N-1에서 시작하여 점차 이동
현재 두 포인터가 가리키는 값의 합을 계산
절대값 비교 및 업데이트
if abs(tmp) < solution : # tmp의 절대값이 solution보다 작을 경우
sol_left = left # sol_left 갱신
sol_right = right # sol_right 갱신
solution = abs(tmp) # solution 갱신
if tmp == 0 : # tmp 가 0이면 정답이므로 즉시 루프 중단
break현재 합의 절대값이 기존 최소값(solution)보다 작다면 : (0에 더 가깝다면)
- 최소값과 두 수의 인덱스를 업데이트
- 합이 0이라면 정답이므로 탐색 중지
포인터 이동
if tmp < 0 : # tmp < 0 이라면
left += 1 # left 를 오른쪽으로 한 칸 이동
else : # tmp > 0 이라면
right -= 1 # right 를 왼쪽으로 한 칸 이동합(tmp)이 음수라면 left 를 오른쪽으로 한 칸 이동
- 작은 값을 줄이기 위해
합이 양수라면 right를 왼쪽으로 한 칸 이동
- 큰 값을 줄이기 위해
이 글을 적으면서 이해가 안 되었던 부분이 해결되었다.
- sol_left와 sol_right를 쓰는 부분이 이해가 되지 않았다. => 이 부분 때문에 문제 해결 하지 못했음.
- 최소값을 저장하기 위해 따로 저장을 하였구나.
생각보다 재밌었던 문제였다고 생각한다.
투 포인터 vs 이분 탐색
이분 탐색으로도 풀 수 있다.
# 1. 데이터 입력 받기
N = int(input())
arr = list(map(int, input().split()))
solution = float('inf')
sol_left = sol_right = 0
# 2. 각 원소에 대해 이분 탐색
for i in range(N - 1) :
curr = arr[i]
left, right = i + 1, N - 1
# 3. 이분 탐색 구현
while left <= right :
mid = (left + right) // 2
tmp = curr + arr[mid]
# 4. 최소값 갱신
if abs(tmp) < solution :
sol_left = i
sol_right = mid
solution = abs(tmp)
if tmp == 0 :
break
# 5. 포인터 이동
if tmp < 0 :
left = mid + 1
else :
right = mid - 1
print(arr[sol_left], arr[sol_right])- 투 포인터 알고리즘
- 시간 복잡도
- 리스트를 처음부터 끝까지 한 번 훑으므로 O(N).
- 정렬된 리스트를 입력받았기 때문에 정렬에 따른 추가 복잡도는 없습니다.
- 공간 복잡도
- 입력 리스트를 그대로 사용하며, 추가 공간 사용은 상수 개수의 변수뿐이므로 O(1).
- 시간 복잡도
- 이분 탐색 알고리즘
- 시간 복잡도
- 외부 루프 : 각 원소에 대해 O(N)
- 내부 이분 탐색 : 범위 N에서 절반씩 줄어들기 때문에 O(log N)
- 전체 시간 복잡도 : O(N log N)
- 공간 복잡도
- 추가적인 데이터 구조 없이 상수 개수의 변수만 사용 O(1)
- 시간 복잡도
대체로 이런 문제를 풀게 되면 이분 탐색으로 많이 풀었는데 투 포인터라는 개념을 배울 수 있어서 좋았던 문제였다.
이분 탐색에 대해서도 공부를 더 해야할 것 같다. 이 문제는 풀이 방법부터 떠올리기 쉽지 않았다.