[이분탐색/투포인터] 2467,2473

1. 용액

링크 - https://www.acmicpc.net/problem/2467

코드

#용액 22-02-06
import sys

def solution(n,liquid):
    liquid.sort() #정렬하기
    start = 0
    end=n-1 #마지막
    answer=[liquid[start],liquid[end]]
    min_val=abs(liquid[start]+liquid[end])

    while start<end:
        mix = liquid[start]+liquid[end]
        if abs(mix)<min_val:
            min_val = abs(mix)
            answer[0]=liquid[start]
            answer[1]=liquid[end]
        if mix>0: #end를 앞으로 옮겨준다.
            end-=1
        elif mix<0: #start를 뒤로 옮겨준다.
            start+=1
        else:
            print(*answer)
            return answer
    print(*answer)
    return answer

if __name__=="__main__":
    input = sys.stdin.readline
    n = int(input())
    liquid = list(map(int,input().split()))
    solution(n,liquid)

풀이 방법

이분탐색과 투포인터를 사용해서 푸는 문제였다.
입력된 리스트를 정렬한 상태로 진행해야한다.

1. start는 리스트의 맨 앞, end는 리스트의 맨 뒤를 가리키도록 한다.
2. 두 용액을 합쳐서 절댓값이 min_val보다 작다면 정답리스트와 min_val을 교체한다.
3. 두 용액을 합친 값이 0보다 크면 -> end를 앞으로 한 칸 옮긴다.
4. 두 용액을 합친 값이 0보다 작으면 -> start를 뒤로 한 칸 옮긴다.
5. 두 용액을 합친 값이 0이라면 -> 정답리스트를 출력하고 종료한다.

2. 세 용액

링크 - https://www.acmicpc.net/problem/2473

코드

#세 용액 22-02-06 이분 탐색
#2467번에서 용액 하나를 추가로 고정시킨다.
import sys

def solution(n,liquid):
    liquid.sort() #정렬하기
    start =1
    end = n - 1  # 마지막
    answer = [liquid[0], liquid[start], liquid[end]]
    min_val = abs(liquid[0] + liquid[start] + liquid[end])
    for fix in range(n-2): #범위 - 3개 골라야 함
        start = fix+1 #fix 다음부터 시작
        end = n - 1  # 마지막
        while start<end:
            mix = liquid[fix]+liquid[start]+liquid[end]
            if abs(mix)<min_val:
                min_val = abs(mix)
                answer[0] = liquid[fix]
                answer[1]=liquid[start]
                answer[2]=liquid[end]
            if mix>0: #end를 앞으로 옮겨준다.
                end-=1
            elif mix<0: #start를 뒤로 옮겨준다.
                start+=1
            else:
                print(*answer)
                return answer
    print(*answer)
    return answer

if __name__=="__main__":
    input = sys.stdin.readline
    n = int(input())
    liquid = list(map(int,input().split()))
    solution(n,liquid)

풀이 방법

처음에 세 용액 문제를 풀다가 모르겠어서 용액을 푼 뒤 다시 풀었다.
두 용액을 섞었던 앞의 문제에서 세 개로 변형된 문제였다.

로직은 앞의 문제와 똑같으나 고정 값을 추가해서 탐색할 수 있도록 했다. (fix변수)
고정 용액인 fix를 0부터 n-3까지 이동시키면서 나머지 두 용액은 이분탐색과 투포인터를 사용하도록 했다.

.
.
.
이번 기회를 통해서 투포인터를 조금 이해할 수 있었던 것 같다.