<백준> 용액(Gold 5)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2467 용액 at main · heesoo-park/ForCodeKata

제출 결과

---

생각보다는 쉽게 푼 문제였다.

입력값들이 정렬도 되어있고 어떤 걸 써야되겠다는 것도 금방 잡혔기 때문이다.

2중 for문은 데이터 제한이 100000인 걸보고 바로 아니라고 판단했고 투 포인터로 방향을 잡았다.

양쪽 끝에서 시작하여 현재 값이 0보다 큰지 작은지에 맞춰 경계를 줄여나가는 방식이다.

 

0에 가깝다는 기준은 이전에 저장되어있는 값의 절댓값과 현재 계산된 값의 절댓값을 비교하여 더 작은 값으로 잡았다.

또한 현재 값이 0보다 크다면 오른쪽 경계를 1 줄이고, 0보다 작다면 왼쪽 경계를 1 키웠다.

이 부분에서 현재 값을 사용하지 않고 이전에 저장되어있는 값을 사용한 거에 대해 이상함을 느끼지 못하고 다른 데만 계속 수정해서 내다보니 틀렸습니다를 많이 보게 됐다.

이전에 저장되어있는 값은 0에 가까워질 때만 업데이트가 되기 때문에 매번 경계를 줄이는 부분에서는 현재 계산된 값을 사용하는 게 맞는 것이었다.

 

투포인터는 확실히 2중 for문을 대체해서 사용하는 케이스가 많은 거 같다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*
import kotlin.math.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val n = br.readLine().toInt()
    val solutions = br.readLine().split(' ').map { it.toInt() }
    
    var min = -1
    var max = -1
    var sum = 2000000000
    
    var left = 0
    var right = n - 1
    while (left < right) {
        if (abs(solutions[right] + solutions[left]) < abs(sum)) {
            min = solutions[left]
            max = solutions[right]
            sum = max + min   
        }
        
        if (solutions[right] + solutions[left] < 0) left++ else right--
    }
    
    bw.write("$min $max")
    bw.flush()
    bw.close()
}