백준 2467 - 골드5 - Python

정답 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
nli = list(map(int,input().split()))

l, r = 0, n-1
mn = float('inf')
rs1,rs2 = 0,0
while l < r:
    a,b = nli[l],nli[r]
    if abs(a + b) < mn:
        mn = abs(a + b)
        rs1,rs2 = a,b
    if a + b < 0:
        l += 1
    elif a + b > 0:
        r -= 1
    else:
        break

print(rs1,rs2)

# 제출번호 : 96583643, 메모리 : 44748, 시간 : 132

풀이과정

직관적으로 떠오른 풀이 방식은 O(n^2)를 갖는

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
nli = list(map(int,input().split()))

mn = float('inf')
r1,r2 = 0,0

for i in range(n-1):
    for j in range(i,n):
        a = nli[i]
        b = nli[j]
        if abs(a+b) < mn:
            mn = abs(a+b)
            r1,r2 = a,b

print(r1,r2)

였으나, 문제에서 주어진 최대 100000개의 정수는 이 코드 기준 100억번의 계산이기에 절대 통과 할 수 없을것이당

투 포인터

투 포인터는 정렬된 배열에서 양 끝에서 시작하는 두 포인터를 이용하여 조건에 따라 포인터를 이동 시키는 방법이다. 정렬이 이미 되어있다는 가정 하에 O(n) 의 시간복잡도를 갖는다.

투 포인터는 한 쪽을 선택할 경우 다른 쪽의 선택지가 제한된다라는 특성을 활용하며

• 합이 목푯값보다 크면 -> 큰 값 포인터를 왼쪽으로
• 합이 목푯값보다 작으면 -> 작은 값 포인터를 오른쪽으로

이동하는 과정을 통해 해를 탐색하는 알고리즘이다.

나의 풀이에선 0을 기준으로 절대 값을 이용하여 가장 0에 가까운 두 쌍을 투 포인터를 활용하여 찾은 후 기록, 이를 출력하는 방식으로 구성하였다.

비고

1.

solved.ac Class 5 문제였다.

2.

..예전에 투 포인터 활용해서 문제 풀었었는데.. 6개월 안하니 다 까먹어버렷다..