[BOJ] 2470 두 용액 - python

2470번: 두 용액

2470번: 두 용액

 

풀이

모든 조합의 수를 구한다는건 말도 안됨, 근데 모든 경우의 수를 다 하는 것 밖에 없는데 그렇다면 투 포인터 이용! 하나씩 포인터를 이동해가며 절댓값이 최소가되도록 하는 (양,음을 이용해서 판별) 포인터를 이동시키고, 그 들 중 최솟값을 저장하여 출력한다. 포인터를 이용할 것 이므로 리스트를 소팅한다. 여기서 투 포인터는 양쪽 liquid 인덱스이고, 판단 기준은 '절댓값이 최소가 된다' → '음,양 일 때 각각의 값을 최소로 만들자' → 음,양 중 더 큰 쪽을 움직여서 작게 만들자

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input()) #2<= N <=100,000
liquid = sorted(list(map(int,input().split(" "))))
#print(liquid)

#임의의 두 개를 더해서 0에 가장 가까운 값을 만들어야 함
#다 하는 것 밖에 답이 없는데 그러면 시간 초과가 뜸
#이진 탐색?

#적합 : 음수? 양수?
start = 0
end = len(liquid)-1
s,e = -1,-1
abs_min = float('inf')

while start < end: #두 용액이 같을 수 없으니 등호는 제외
    fit = liquid[start] + liquid[end]

    if abs_min > abs(fit): #최솟값이면 갱신
        s, e = start, end
        abs_min = abs(fit)

    if fit == 0:
        break
    else:
        if fit > 0: #양수가 더 크다는 것이므로 오른쪽 -1
            end -= 1
        else: #음수가 더 크다는 것이므로 왼쪽 +1
            start += 1

print(liquid[s], liquid[e])

얻어가는 것

• 투포인터

  #투 포인터 start, end설정
  start = 0
  end = len(arr) -1
  
  while start < end: #두 포인터가 같지 않아야 할 때는 등호를 뺀다
  	#start,end를 가지고 function 실행
  
  	if function(start,end) == goal:
  			break
  	else:
  			if function(start,end) > goal: 
  					end = mid - 1 #왼쪽만 살림, 오른쪽 제거
  			else:
  					start = mid + 1 #오른쪽만 살림, 왼쪽 제거
  

• → 정렬되어 있는 리스트에서 , N이 엄청나게 큰 수 일 때, 두 개의 포인터를 가지고 , 특정 기준에 따라 데이터를 탐색할 때

느낀점

"211116"

소요 시간 : 1h

• 이진탐색에서 mid이용하는걸로만 생각했는데 이건 투포인터 문제였다
• 머리가 터질 것 같다
• 조건을 어떤 식으로 검색하면 좋을 지 기준을 잘 세우는 연습을 해야겠다