접근

투포인터 알고리즘을 이용하여 푸는 문제였다.

투포인터 알고리즘 설명 및 기본 문제: 2021.04.24 - [코딩/백준 (Python)] - 백준 3273번: 두수의 합 (Python)

 

백준 3273번: 두수의 합 (Python)

접근 먼저 투포인터 알고리즘에 대해 알아보았다. 위 문제를 가장 직관적인 방법으로 푸는 방법은 2중 for문을 순환하면서 두 수의 합이 원하는 값을 표시할때마다 카운트해주는 것이다. 하지만

ca.ramel.be

기존 투포인터 알고리즘과 동일하게 용액들을 오름차순으로 정렬한 후 탐색하되, 두 용액을 합한 특성값이 0보다 크면 right를 1 줄여주고 0보다 작으면 left를 1 키워주었다. 연산을 진행하는 동안 두 용액 특성 값의 절대값을 계속 갱신하면서 절대값이 작을때의 두 용액을 저장해주고, 특성 값이 0이 나오면 이후 탐색할 필요가 없으므로 break 해준다.

코드

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

nums.sort()
left, right = 0, n - 1
ans = [float('inf'), 0, 0]
while left < right:
    tmp = nums[left] + nums[right]
    if abs(tmp) < ans[0]:
        ans = [abs(tmp), nums[left], nums[right]]
    if tmp > 0:
        right -= 1
    elif tmp < 0:
        left += 1
    else:
        ans = [abs(tmp), nums[left], nums[right]]
        break
print('{} {}'.format(ans[1], ans[2]))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기