백준 2295번 세 수의 합 Kotlin 구현해보기

---

```

백준 2295번 세 수의 합 Kotlin 구현해보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1. 백준 2295번 풀이

---

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

2295번: 세 수의 합

 

백준 2295번 세 수의 합은

난이도 골드 등급의 문제로서

 

5개 이상 1000개 이하의 200,000,000 보다 작은 정수를 가진 집합이 주어질 때

집합 내부의 각기 다른 원소 x, y, z를 더해서

집합 내부의 수가 될 수 있는

가장 큰 수를 구해주면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

단순하게 비교하면 O(n^3) 이기 때문에 복잡도가 너무 높습니다

 

따라서

x + y + z = u 에서

x + y = u - z로 찾고

x + y는 미리 hashmap이나 List로 구해서 아래와 같이 비교한 다음

twoNums.binarySearch(oneNums[j] - oneNums[i]) >= 0

비교된 값 중 최대 값을 찾아주면 됩니다.

 

 

전체 코드는 아래와 같습니다

import kotlin.math.max

fun main(args: Array<String>) {
    // 입력
    val size = readln().toInt()
    val oneNums = ArrayList<Int>()
    val twoNums = ArrayList<Int>()

    for (i in 0 until size) {
        oneNums.add(readln().toInt())
    }
    oneNums.sort()

    for (i in 0 until size) {
        for (j in i until size) {
            twoNums.add(oneNums[i] + oneNums[j])
        }
    }
    twoNums.sort()

    // 출력
    print(findSumOfThree(size, oneNums, twoNums))
}

fun findSumOfThree(size: Int, oneNums: ArrayList<Int>, twoNums: ArrayList<Int>): Int {
    var ans = 0
    for (i in 0 until size) {
        for (j in i + 1 until size) {
            if (twoNums.binarySearch(oneNums[j] - oneNums[i]) >= 0) {
                ans = max(ans, oneNums[j])
            }
        }
    }
    return ans
}

// https://codemasterkimc.tistory.com/

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---