2 minute read

문제

접근 방법

모든 경우의 수를 확인하여 합의 절대값이 0과 제일 가까운 짝을 찾으려면 $O(N^2)$의 시간이 소요된다. 따라서 다른 방법을 적용해야 하는데 짧은 시간으로 전체를 순회하는데 사용되는 방법은 두 가지다.

1) 두 포인터 2) 이분 탐색

나는 처음에 두 포인터로 풀었지만 조금 비효율적(?)으로 풀었다. 나는 양수와 음수들을 따로 분리해서 양수들은 오름차순, 음수들은 내림차순으로 정렬하였다. 양수 포인터와 음수 포인터를 따로 만들고 합이 음수라면, 양수 쪽을 높여야 더 0에 가까워지므로 양수 포인터를 옮기고 합이 양수라면 음수 쪽을 더 낮춰야 더 0에 가까워지므로 음수 포인터를 옮겼다. 이 방법을 통해 O(N)으로 전체 data를 순회하면서 풀었다.

첫 풀이 코드

import sys
input = sys.stdin.readline

"""
양수와 음수를 나눈 뒤, 음수는 내림차순으로, 양수는 오름차순으로 정렬

양수의 시작점은 작은 수, 음수의 시작점은 큰 수.

양수 pointer와 음수 pointer로 전체 data를 순회

두 수의 합이 양수라면 음수 pointer를 움직이고 음수면 양수 pointer를 움직이면 된다.
"""
min_val = int(2e9)
ans_1, ans_2 = 0,0
n = int(input())
liqs = list(map(int, input().split()))

pos = []
neg = []
for liq in liqs:
  if liq>=0:
    pos.append(liq)
  else:
    neg.append(liq)

pos.sort()
neg.sort(reverse=True)
pos_len = len(pos)
neg_len = len(neg)

# 양수만 있을 경우에는 제일 작은 애들 두개가 답 + 양수에만 답이 있는 경우 
if pos_len >= 2:
  min_val = min(min_val,pos[0]+pos[1])
  ans_1, ans_2 = pos[0], pos[1]

# 음수만 있을 경우에는 제일 큰 애들 두개가 답 + 음수에만 답이 있는 경우
if neg_len >= 2:
  if abs(neg[0]+neg[1]) < min_val:
    min_val = abs(neg[0]+neg[1])
    ans_1, ans_2 = neg[1], neg[0]
  
# 양수, 음수 둘 다 있을 경우 pointer 사용
if neg_len > 0 and pos_len > 0:
  pp, np = 0,0
  while pp<pos_len and np<neg_len:
    summ = pos[pp]+neg[np]
    if abs(summ) < min_val:
      ans_1, ans_2 = neg[np], pos[pp]
      min_val = abs(summ)
    if summ < 0:
      pp+=1
    else:
      np+=1

print(f"{ans_1} {ans_2}")

하지만 그냥 전체 data가 오름차순으로 되어있기 때문에 처음과 끝을 두 포인터로 만들고 양수 음수 나눌 거 없이 합이 양수면 큰 수를 가리키는 끝 포인터가 왼쪽으로, 합이 음수면 작은 수를 가리키는 시작 포인터가 오른쪽으로 가면 되는거였다… 이렇게 하면 전체 데이터의 양수 개수, 음수 개수를 확인하면서 예외처리를 할 필요가 없어진다.

정답 코드 (1) O(N)

import sys
input = sys.stdin.readline

"""
투 포인터로 양끝에서 합이 0 이상이면, 양수 pointer를 왼쪽으로 합이 0 이하면 음수 pointer를 오른쪽으로 옮기면서 푼다.
"""

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

start = 0
end = n-1
min_val = int(2e9)
ans1, ans2 = 0, 0
while start < end:
  summ = liqs[start] + liqs[end]
  if summ == 0:
    ans1, ans2 = liqs[start], liqs[end]
    break
  if abs(summ) < min_val:
    min_val = abs(summ)
    ans1, ans2 = liqs[start], liqs[end]

  if summ < 0:
    start+=1
  else:
    end -= 1
print(f"{ans1} {ans2}")

다음은 이분 탐색을 사용하는 것이다. 이 풀이는 생각을 하기 했지만 O(N)은 안 될 거 같아서 안 짰다… 정렬을 한 후, 모든 수에 대해 그 수와 합쳐서 0보다 작으면 start를 옮겨서 탐색 범위를 더 큰 수 쪽으로, 0보다 크면 end를 옮겨 탐색 범위를 더 작은 수 쪽으로 좁혀서 최적의 수를 찾으면 된다. 이렇게 하면 대충 O(NlogN)이다.

정답 코드 (2) O(NlogN)

import sys
input = sys.stdin.readline

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

min_val = int(2e9)
ans_1, ans_2 = -1, -1
for i in range(n-1):
  cur = liqs[i]
  start = i+1
  end = n-1
  while start<=end:
    mid = (start+end)//2
    summ = cur + liqs[mid]
    if abs(summ) < min_val:
      min_val = abs(summ)
      ans_1, ans_2 = i, mid

      if summ == 0:
        break
      
    if summ < 0:
      start = mid+1

    else:
      end = mid-1

print(f"{liqs[ans_1]} {liqs[ans_2]}")

You May Also Enjoy