세 용액 (2473번) - 백준 (BOJ)

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

2473번: 세 용액

 

 

백준 - 세 용액 (2473번)

 

난이도 : Gold 3

알고리즘&자료구조 : Two-pointer (투 포인터) & Sorting (정렬)

시간복잡도 (Time Complexity) : O( N^2 )

 

---

 

정렬과 투 포인터를 적절히 활용해서 해결할 수 있는 문제이다.

 

 

< 전체 코드 >

def _search(N, arr):
    maxy = 3_000_000_000
    answer = [0, 0, 0]
    for i in range(N-2):
        s, e = i+1, N-1
        while s < e:
            cur = arr[i] + arr[s] + arr[e]
            if cur > 0:
                if cur < maxy:
                    maxy = cur
                    answer = [arr[i], arr[s], arr[e]]
                e -= 1
            elif cur < 0:
                if -cur < maxy:
                    maxy = -cur
                    answer = [arr[i], arr[s], arr[e]]
                s += 1
            else:
                return [arr[i], arr[s], arr[e]]
     	if 0 <= arr[i]:
            break
    return answer


class Liquids():
    def __init__(self, N, arr):
        arr.sort()
        if 3 <= sum(True for val in arr if val == 0):
            self.answer = [0, 0, 0]
        elif 0 <= arr[0]:
            self.answer = arr[:3]
        elif arr[-1] <= 0:
            self.answer = arr[-3:]
        else:
            self.answer = _search(N, arr)


if __name__ == "__main__":
    fluids = Liquids(int(input()), list(map(int, input().split())))
    print(*fluids.answer)

 

---

 

▶ 주어진 배열 arr을 오름차순으로 정렬한다.

arr.sort()

 

 

 

ⓐ 주어진 배열 arr에 0이 3개 이상 존재한다면,

[0, 0, 0] 의 합으로 0을 만들 수 있으므로 정답은 0이 된다.

if 3 <= sum(True for val in arr if val == 0):
    self.answer = [0, 0, 0]

 

 

 

ⓑ 주어진 배열 arr에서 가장 작은 값이 0보다 크거나 같다면,

arr에서 가장 작은 값 3개를 나열한 것이 정답이 된다.

elif 0 <= arr[0]:
    self.answer = arr[:3]

 

 

 

ⓒ 주어진 배열 arr에서 가장 큰 값이 0보다 작거나 같다면,

arr에서 가장 큰 값 3개를 나열한 것이 정답이 된다.

elif arr[-1] <= 0:
    self.answer = arr[-3:]

 

 

 

ⓓ 위의 ⓐ ⓑ ⓒ 중 어느 것에도 해당되지 않는다면,

투 포인터를 활용해서 0에 가장 가까운 3개의 용액의 합을 찾는다.

def _search(N, arr):
    maxy = 3_000_000_000
    answer = [0, 0, 0]
    for i in range(N-2):
        if 0 <= arr[i]:
            break
        s, e = i+1, N-1
        while s < e:
            cur = arr[i] + arr[s] + arr[e]
            if cur > 0:
                if cur < maxy:
                    maxy = cur
                    answer = [arr[i], arr[s], arr[e]]
                e -= 1
            elif cur < 0:
                if -cur < maxy:
                    maxy = -cur
                    answer = [arr[i], arr[s], arr[e]]
                s += 1
            else:
                return [arr[i], arr[s], arr[e]]
    return answer

 

ⓓ-① 세 용액의 합이 가장 0에 가까웠던 값을 저장할 maxy를 초기화한다.

for 문을 활용해서 [0 ~ (N-2)] 까지 인덱스 i를 탐색한다.

만약 arr[i] 가 0보다 크거나 같아지면, break로 반복문을 중단한다.

for i in range(N-2):
    if 0 <= arr[i]:
        break

 

ⓓ-② 각 인덱스 i에 대해서, [(i+1) ~ (N-1)] 범위에 투 포인터를 적용한다.

(s = i+1), (e = N-1) 로 두고, s < e 일 때까지 while 문을 진행한다.

        s, e = i+1, N-1
        while s < e:

 

세 용액의 합인 arr[i] + arr[s] + arr[e] 값이 0보다 크면

cur 값을 작게 만들기 위해 e에서 1을 빼준다.

 

arr[i] + arr[s] + arr[e] 값이 0보다 작으면

cur 값을 크게 만들기 위해 s에 1을 더해준다.

 

만약 현재 계산한 용액들의 합 cur이,

현재까지 0에 가장 가까웠던 값보다 더 0에 가깝다면

maxy를 cur로 업데이트 해준다.

또한 answer에 세 용액 [answer[i], answer[s], answer[e]] 를 저장해둔다.

 

            cur = arr[i] + arr[s] + arr[e]
            if cur > 0:
                if cur < maxy:
                    maxy = cur
                    answer = [arr[i], arr[s], arr[e]]
                e -= 1
            elif cur < 0:
                if -cur < maxy:
                    maxy = -cur
                    answer = [arr[i], arr[s], arr[e]]
                s += 1

 

만약 cur = 0 이라면, 더 이상 찾을 필요가 없으므로

현재 용액의 조합인 [answer[i], answer[s], answer[e]] 을 바로 return 해준다.

            else:
                return [arr[i], arr[s], arr[e]]

 

 

 

▶ 위에서 찾은 answer 값을 출력해준다.

print(*fluids.answer)