[Python/백준] 2467번: 용액 - 투포인터

1. 문제 

2467번: 용액

2. 해결방법 

정렬해서 주어진 배열, 처음과 마지막에서 점점 좁혀들어오는 방식으로 푸는 문제인 점을 고려하여

투포인터 알고리즘을 사용하니 쉽게 해결되었다 ! 

우선 투포인터까지 구현은 어렵지 않았으나 .. '특성값이 0에 가까운 용액을 만들어내는 두 용액의 특성값'을 구하는 것이 난관이었다. 

 

생각을 해보잣 ... ! 

 

(1) 새로운 리스트를 만들어서 투포인터로 돌면서 (start,end)값을 넣어준 뒤  min(abs(start,end의 두용액의 특성값)))을 어찌저찌 구하면 어떨까.. 생각을 해보았다. 구현해보진 않았지만 파이썬에서 배열은 시간을 많이 잡아먹고 아무리 투포인터라도 꽤 많은 수를 배열에 넣어서 다시 min 함수를 통해 찾고 반환하고 .... 시간초과 우려가 다분히 있어 다른 방법을 생각해보았다. 

 

(2) 값을 갱신하는 것이 가장 좋을 것이라 생각했다. start, end값을 ans_start, ans_end의 solution값에 넣은 합의 절댓값을 비교해서 작으면 ans갱신, 아니면 넘어가는 방식으로 가장 작은 값을 찾을 수 있다고 생각했다. 만약 solution[start] + solution[end] = 0이라면 언제나 이 값이 답일 것이고 랜덤으로 반환해주면 되니 그냥 ans 에 바로 넣어주면 된다 ! 

 

자세한 건 코드로 보자 ~ ~

 

 

3. 코드 

n = int(input())

solution = list(map(int,input().split()))


start,end = 0,n-1

ans_start, ans_end = 0,n-1
while start<end:
    # start가 가르키는 절댓값이 end 가 가르키는 절댓값보다 작다. -> start가 이동 !
    if solution[start] + solution[end] < 0:
        # 갱신
        if abs(solution[start]+solution[end]) < abs(solution[ans_start]+solution[ans_end]):
            ans_start, ans_end = start,end
        start += 1
    # start가 가르키는 절댓값이 end가 가르키는 절댓값보다 크다 -> end 이동
    elif solution[start] + solution[end] >0:
        # 갱신
        if abs(solution[start]+solution[end]) < abs(solution[ans_start]+solution[ans_end]):
            ans_start, ans_end = start, end
        end -= 1
    else:
        ans_start, ans_end = start, end
        start+=1
        end-=1
print(solution[ans_start],solution[ans_end])