[PY] 2470 : 두 용액

 

https://www.acmicpc.net/problem/2470

나의 생각은..

1. 모든 입력을 받고나서 정렬하고 음수 양수를 각자의 배열로 분리한다.
2. 음수 하나를 선택하고 해당 음수와 더해질때 0이 되는 숫자인 양수를 찾기위해 -1을 곱해서 해당 숫자를 이분 탐색 시도한다.
   1. 이분 탐색을 한다면 동일한 숫자는 못찾아와도 근처의 숫자까지는 시도 후 그 값을 반환 할 것이라는 판단에서 기안했다.
3. 그럼 답에 그나마 가까운 이 내용와 비교하고 이 내용의 합산에 따라 0에 이전 저장값보다 가깝다면 갱신한다.

문제는

5

-100 1 2 3 4

하면 개 박살이 났다. 그래서 다른 사람들 코드를 보니 너무 정직하게 쓴 걸 통과하는걸 보고 너무 나한테 속상했다.

다른 사람 코드의 아이디어는 이렇다.

1. 모든 입력을 받고나서 정렬하고, 첫 기준 점은 최대로 나올 수 있는(20억쯤) 수와 min 비교를 한다.
   1. 여기서는 입력을 정렬한 배열을 가리키는 포인터는 맨 처음과 맨 끝 두 개로 하기로 한다.
2. 그냥 min이 아닌 절댓값 상에서의 min을 세야하니 0에서 떨어진 거리가 적으면 적을수록 해당 수로 갱신 되게 된다.
3.  그리고 절댓값으로 변환하기 전의 수치를 0보다 큰지 아닌지를 보면, 포인터를 조정해서 수를 조정해야 함을 알게 된다.
   1. 처음에서 시작한 포인터의 위치 조정 : 반드시 결과가 증가한다
   2. 끝에서 시작한 포인터의 위치 조정 : 반드시 결과는 감소한다
4. 결국에는 0을 왔다갔다 거리지만 0에 도착 할 수도있고 그 언저리에 있을 수도 있는 두 조합을 찾는 코드였다.

개잘하내.

실패 코드

import sys

    # 양수나 음수 쪽 배열에서 아이템을 하나 잡고 남은 한쪽에서 제일 적절한 수를 찾는데 의의를 갖는다..
        # 예를 들어 -2 입장에서 3 4 5 6 7 8 9를 찾아야하면 당연히 찾을 값은 2가 될 것이다.
        # 그럼 양수 입장에서 2를 찾는 이분 탐색을 시도 하는 것이다.
        # 3 4 5 [6] 7 8 9는 너무 크니 범위를 줄인다.
        # 3 4 5 6
        # 3 [4] 5 6 여전히 크다.
        # 3
        # [3] 3은 여전히 크고 찾을 수는 없었다. 하지만 찾고자하는 2에는 제일 가깝다.
        # 보통의 이분 탐색이라면 검색 실패지만 유사 치를 찾는 것이니 이건 제일 적절하다.

        # 이런식으로 음수에서 값을 pick 한다음 가장 적합한 값을 찾는다.
        # 0에 가까운 경우는 음수, 양수, 값 순으로 값을 갱신하고 값을 기준으로 이 튜플이 변경되도록 한다.
        # 마지막엔 음수, 양수 순으로 출력하고 프로그램이 끝난다.
        



caseCnt = int(sys.stdin.readline())
numField = list(map(int, sys.stdin.readline().strip().split()))[:caseCnt]
onlyPlus = []
onlyMinus = []

ansPlus = 0
ansMinus = 0
ans = 1000000000

def binarySearch(str, end, target):
    lastestVisited = 0

    while(str <= end):
        mid = (str + end) // 2
        
        if(onlyPlus[mid] == target):
            lastestVisited = onlyPlus[mid]
            return lastestVisited

        if(onlyPlus[mid] > target):
            end = mid - 1
        else:
            str = mid + 1
        lastestVisited = onlyPlus[mid]

    if(str > end):
        return lastestVisited

numField.sort()

for i in range(len(numField)):
    if(numField[i] > 0):
        onlyPlus.append(numField[i])
    else:
        onlyMinus.append(numField[i])

if(len(onlyMinus) == 0):
    ansMinus = onlyPlus[0]
    ansPlus = onlyPlus[1]
    ans = ansMinus + ansPlus
elif (len(onlyPlus) == 0):
    ansPlus = onlyMinus[len(onlyMinus) - 1]
    ansMinus = onlyMinus[len(onlyMinus) - 2]
    ans = abs(ansMinus + ansPlus)
else:
    for i in range(len(onlyMinus)):
    # 음수 하나 픽, 이거에 제일 적합한 음수 찾기.
    # 어쨌든 이분 탐색은 제일 가까운 답을 뱉게 된다.
        targetNum = -1 * onlyMinus[i]
        expectedNum = binarySearch(0, len(onlyPlus) - 1, targetNum)
        tmpAns = abs(targetNum - expectedNum)
        if(ans > tmpAns):
            ans = tmpAns
            ansMinus = onlyMinus[i]
            ansPlus = expectedNum
    # 그 답과 더해서 나온 값이 최저치라면, 답을 갱신해야한다.
    # 답의 저장 양식은 3개이다 : ansPlus, ansMinus, ans


    # 문제 :
    # minus가 아예 없거나 plus가 아예 없는 경우를 고려해야한다.

    for i in range(len(onlyPlus) - 1):
        tmpMin = onlyPlus[i]
        tmpMax = onlyPlus[i + 1]
        tmpAnswer = abs(tmpMin + tmpMax)
        if(ans > tmpAnswer):
            ans = tmpAnswer
            ansMinus = tmpMin
            ansMax = tmpMax

    for i in range(len(onlyMinus) - 1, 1, -1):
        tmpMin = onlyMinus[i - 1]
        tmpMax = onlyMinus[i - 2]
        tmpAnswer = abs(tmpMin + tmpMax)

        if(ans > tmpAnswer):
            ans = tmpAnswer
            ansMinus = tmpMin
            ansMax = tmpMax

print(f"{ansMinus} {ansPlus}")

 

정답 처리 코드

import sys

caseCnt = int(sys.stdin.readline())
numField = list(map(int, sys.stdin.readline().strip().split()))[:caseCnt]

numField.sort()

startIdx = 0
endIdx = caseCnt - 1
numA = 1000000000
numB = 1000000001

while startIdx != endIdx:
    if(abs(numField[startIdx] + numField[endIdx]) < abs(numA + numB)):
        numA = numField[startIdx]
        numB = numField[endIdx]

    if(numField[startIdx] + numField[endIdx] < 0):
        startIdx += 1
    else:
        endIdx -= 1


print(f"{numA} {numB}")