백준 2467번 용액 - SWIFT

문제

---

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

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

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

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

 

입력

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

 

출력

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

 

문제 링크

2467번: 용액

 

 

풀이

---

투 포인터 알고리즘으로 배열을 순회하면서 값을 대입하면 된다.

하지만 우리는 0에 가장 가까운 두 값의 합을 구하는 것이기 때문에, 구간의 합을 구하는 방식과는 다르게 구현해야한다.

 

접근법

두 용액을 더했을 때 0과 근접하려면, 부호가 다른 두 값을 더하는게 가장 좋다.

그리고 절대값이 큰 값의 경우, 절대값이 큰 반대 부호의 값을 더해야 0과 근접해진다.

그래서 일단 음수와 양수가 분리될 수 있게끔, 정렬을 해준다.

그리고 두 개의 포인터를 이용하는데, 하나는 왼쪽 맨 끝인 음수 영역, 다른 하나는 오른쪽 맨 끝인 양수 영역에 놓고 값을 더해보면 된다.

이렇게 하는 경우, 모두 같은 부호의 값일 경우 비효율적으로 바뀐다는 문제가 있지만, 최악의 상황도 결국엔 배열의 개수인 O(N)이 되어 큰 문제는 없다.

 

프로그램 동작

---

1. 가장 먼저 들어온 수를 크기 순서로 정렬한다.▼

 

 

2. 정렬된 배열의 가장 왼쪽을 left포인터, 가장 오른쪽을 right 포인터로 두 포인터를 설정해준다.▼

 

 

3. 그리고 두 포인터가 가리키고 있는 값을 더한다.

그렇게 해서 나온 값을 정답 튜플에 있는 값과 비교해서 넣어준다.

정답 튜플의 초기에는 최대 값이 들어있다.▼

 

 

정답 튜플의 값과 두 포인터가 가리킨 값의 합의 절대값 중 더 작은 값을 넣어준다.

만약 두 포인터가 가리킨 값의 합이 더 작았다면, 두 포인터 위치도 같이 넣어준다.

정답 튜플 값이 더 작았다면, 그대로 둔다.

나온 값이 0보다 작았으므로, 다음에 더했을 때의 값을 좀 더 키워주기 위해 left 포인터 값을 하나 늘려준다.▼

 

 

4. 이번에도 정답 튜플에 들어있는 값보다 절대값이 작으므로 값을 갱신해준다.

마찬가지로, 나온 값이 음수이므로 left 포인터 값을 하나 늘려준다.▼

 

 

5. 이번에도 여전히 나온 절대값이 더 작으므로 값을 갱신해준다.

하지만 이번엔 나온 값이 양수이므로, right 포인터 값을 하나 감소시킨다.▼

 

 

6. 이번 값도 절대값이 더 작으므로 값을 갱신해준다.

이번에도 전과 같인 양수값이 나왔으므로, right 포인터 값을 하나 감소시킨다.▼

 

 

7. 이번에는 0값이 나왔다.

절대값의 영역에서는 0이 최소이므로, 다음 값은 보지 않고 값을 저장하고 종료시킨다.▼

 

만약 계속 순회해도 0이 나오지 않는다면, left와 right가 같아졌을 때 종료시킨다.

 

 

Swift 코드

---

import Foundation 

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] 
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } 
        if now == 45{ isPositive.toggle(); now = read() } 
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() } 

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

var file = FileIO()
let N = file.readInt()
var liquid = Array(repeating: 0, count: N)
for i in 0..<N {
    liquid[i] = file.readInt()
}
var left = 0
var right = N - 1
var answer = (0, 0, 2100000000)

while left < right {
    let sum = liquid[left] + liquid[right]

    if sum < 0 {
        if abs(sum) < answer.2 {
            answer.0 = liquid[left]
            answer.1 = liquid[right]
            answer.2 = abs(sum)
        }
        left += 1
    } else if sum > 0 {
        if abs(sum) < answer.2 {
            answer.0 = liquid[left]
            answer.1 = liquid[right]
            answer.2 = abs(sum)
        }
        right -= 1
    } else {
        answer.0 = liquid[left]
        answer.1 = liquid[right]
        answer.2 = abs(sum)
        break
    }
}

print(answer.0, answer.1)