[Algorithm] 백준 BOJ 2467 용액 python 파이썬 투포인터 골드5

Private 난이도 : ♥♥♡♡♡

2467번: 용액

n=int(input())
seq=list(map(int,input().split(' ')))
start=0
end=n-1

candidate=list() # [더한 특성값, 그 때 용액 1, 그 때 용액 2]
while start<end:
    value=seq[start]+seq[end] # 더한 특성값
    candidate.append([abs(value),seq[start],seq[end]]) # 저장 # 음수,양수에 상관없이 특성값 저장
    if value==0: # 이보다 더 좋은 경우는 없음
        break
    elif value>0: # 0에 가까워져야 하니 작아져야함
        end-=1
    else:
        start+=1 # 0에 가까워져야 하니 커져야함
candidate.sort() # 특성값이 작은 것부터 sort됨 -> 특성값이 list 중 맨 앞에 있기 때문
print(candidate[0][1],candidate[0][2]) # 만족하는 것 중 아무거나 출력해도 되니 0번 출력

 

 

 

설명

• input의 양 끝에서 시작해서 하나하나씩 포인터를 옮긴다
• 현재의 더해진 특성값을 기준으로
  • 0보다 크면 0과 가까워져야하니 작아져야 한다. → end - 1
  • 0보다 작으면 0과 가까워져야하니 커져야 한다. → start + 1
• 모든 경우의 수 보다는 조금 더 적은 경우를 저장할 수 있게 된다.
• 매 경우마다 candidate에 저장
• candidate를 sort하여 특성값 절대값이 작은 것을 출력

 

 

2470번: 두 용액

사실 이 문제도 입력을 sort만 해주면 정답처리된다.