Two-pointer

김태성·2024년 2월 16일

알고리즘

목록 보기

5/30

처음에는 문제를 보고 meet in the middle 과 같은 방법으로 풀면 되는게 아닌가?
라는 생각을 했다.
그도 그럴것이..

이전문제
N개의 정수로 이루어진 수열이 있을 때, k개의 원소 합이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

이번문제
N개의 정수로 이루어진 수열이 있을 때, 3개의 원소 합이 0에 가까운 수를 구하는 프로그램을 작성하시오.

물론 의역이 좀 있긴 하지만 문제의 개념은 위와 같다.
그래서 와 점수 개꿀이네 ㅋㅋ 하고 덤볐다가..
결국 오늘도 3시간이 증발해버렸다.
요즘 점수 날로먹을려다가 벌받는 느낌이다.

백준 2473 세 용액
https://www.acmicpc.net/problem/2473

문제
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.

입력
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

이 문제는 단순히 combination을 써도 답이 나오긴 한다.

for number in range(4):
    for sub in combinations(arr1, number):
        sub1[number].append(sub)
        
for number in range(4):
    for sub in combinations(arr2, number):
        sub2[number].append(sub)
        

for i in range(len(sub1[1])):
    for j in range(len(sub2[2])):
        if abs(sum(sub1[1][i]) + sum(sub2[2][j])) < abs(sum(ans)):
            ans = sub1[1][i]+sub2[2][j]
            
for i in range(len(sub1[2])):
    for j in range(len(sub2[1])):            
        if abs(sum(sub1[2][i]) + sum(sub2[1][j])) < abs(sum(ans)):
            ans = sub1[2][i] + sub2[1][j]

for i in range(len(sub1[3])):            
        if abs(sum(sub1[3][i])) < abs(sum(ans)):
            ans = sub1[3][i]
            
for i in range(len(sub2[3])):            
        if abs(sum(sub2[3][i])) < abs(sum(ans)):
            ans = sub2[3][i]

대충 이런 끔찍한 짓을 해서 다 더할려고 했으나 바로 메모리 초과가 터졌다.
이후

arr1 = arr[:N//2]
arr2 = arr[N//2:]

ans = [1000000000,1000000000,1000000000]

for number in range(4):
    for subA in combinations(arr1,number):
        for subB in combinations(arr2,3-number):
            if abs(sum(subA) + sum(subB)) < abs(sum(ans)):
                ans = subA+subB
print(*ans)

정신못차리고 이딴짓 했다가 시간초과가 걸렸다.
나름 5줄로 깔끔하게 짰다고 좋아했었는데 지금 생각하면 참담하다.
그래서 다른 방법이 필요했다.

투 포인터 알고리즘을 아주 잘 설명해 주는 그림이다.
우선 왼쪽 끝과 오른쪽 끝을 기준으로 잡고, 그 합이 작다면 left값을 오른쪽으로, 크다면 right 값을 왼쪽으로 옮기면 된다.

여기서 당연하지만 중요한 것이,
list는 정렬 되어 있어야 한다!
이 개념 역시 간단하지만 n^3이 나올수도 있는 알고리즘에 log를 붙여주는 강력한 알고리즘이다.

import sys
N = int(input())
arr = sorted(list(map(int,sys.stdin.readline().split())))

ans = [1000000000,1000000000,1000000000]

for i in range(N-2):
    left = i+1
    right = N-1
    
    while(left<right):
        arrsum = arr[left] + arr[right] + arr[i]
        anssum = sum(ans)
        if(abs(arrsum) < abs(anssum)):
            ans = [arr[left] , arr[right] , arr[i]]
            
        if(arrsum > 0):
            right -= 1
        elif(arrsum < 0):
            left += 1
        elif(arrsum == 0):
            ans.sort()
            print(*ans)
            sys.exit()
ans.sort()
print(*ans)