[백준] 2295 세 수의 합

 

🔒 문제

 

🧠 아이디어

세 수의 모든 조합을 구해서 해당 숫자가 집합 내에 존재하는지 확인하는 풀이를 떠올릴 수 있다.

무적권 시간초과

그러나 시간초과가 반드시 걸리기 때문에

세 수의 합이라는 상황을 두 수의 합 + 나머지 한 수 == 결과 값 k 라는 식을 변형하여 시간복잡도를 낮추는데 있다.

 

 

이로서

$$ O(N^2 \,Log_2N) $$

시간 복잡도로 풀이할 수 있다.

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val nums = IntArray(N)

    repeat(N) {idx->
        nums[idx] = br.readLine().toInt()
    }

    nums.sort()
    
	// N^2
    val prefixSumArr = ArrayList<Int>(N * N)

    for (i in nums.indices) {
        for (j in nums.indices) {
            prefixSumArr.add(nums[i] + nums[j])
        }
    }

    prefixSumArr.sort()

    for (i in nums.indices.reversed()) {
        for (j in nums.indices) {
            if (prefixSumArr.binarySearch(nums[i] - nums[j]) >= 0) {
                print(nums[i])
                return
            }
        }
    }
}

 

 

p.s.

 

두수의 합 집합 내에 존재하는지 여부를 이분탐색이 아니라
HashSet/HashMap 으로 관리하면 더 빠른 풀이가 가능하다.