N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.
입력
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.
출력
M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.
내가 푼 풀이
접근방법: 세그먼트 트리
세그먼트 트리를 어떻게 이용할까 고민을 많이 했는데 답이 잘 안나왔다.
세그먼트 트리는 보통 구간합의 트리로 구성하기 때문에 구간의 합으로 어떻게 최댓값 최솟값을 뽑을까 고민하다가
구간합의 트리가 아닌 구간최솟값 구간최댓값 트리로 만들면 되지않을까 생각했다
세그먼트 트리를 만들 때, 구간에서의 최솟값을 노드에 넣고, 최댓값을 노드에 넣어서 구간합을 구하는 함수도 역시
해당 구간의 모든 노드값의 최소 최대값을 구하게 만들면 될꺼라 생각했다.
세그먼트트리 종류를 두가지 만들고, 구간합을 구하는 함수도 두가지 만들어서 풀었다.
코드로 구현하면 다음과 같다.
import Foundation
// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]
var arr = [0]
for i in 0..<N {
arr.append(Int(readLine()!)!)
}
// 구간최솟값 트리와 구간최댓값 트리 크기 할당
var minTree = Array(repeating: 0, count: arr.count * 4)
var maxTree = Array(repeating: 0, count: arr.count * 4)
// 구간최솟값 세그먼트 트리 생성함수
func sgMinInit(_ start: Int,_ end: Int,_ index: Int) -> Int{
if start == end {
minTree[index] = arr[start]
return minTree[index]
}
let mid = (start+end)/2
minTree[index] = min(sgMinInit(start, mid, index*2), sgMinInit(mid+1, end, index*2+1))
return minTree[index]
}
// 구간최솟값 세그먼트 트리의 구간최솟값 구하기
func sgMin(_ start: Int,_ end: Int,_ index: Int,_ left: Int,_ right: Int) -> Int {
if left > end || right < start { return Int.max }
if left <= start && right >= end {
return minTree[index]
}
let mid = (start+end)/2
return min(sgMin(start, mid, index*2, left, right), sgMin(mid+1, end, index*2+1, left, right))
}
// 구간최댓값 세그먼트 트리 생성함수
func sgMaxInit(_ start: Int,_ end: Int,_ index: Int) -> Int{
if start == end {
maxTree[index] = arr[start]
return maxTree[index]
}
let mid = (start+end)/2
maxTree[index] = max(sgMaxInit(start, mid, index*2), sgMaxInit(mid+1, end, index*2+1))
return maxTree[index]
}
// 구간최댓값 세그먼트 트리의 구간최댓값 구하기
func sgMax(_ start: Int,_ end: Int,_ index: Int,_ left: Int,_ right: Int) -> Int {
if left > end || right < start { return Int.min }
if left <= start && right >= end {
return maxTree[index]
}
let mid = (start+end)/2
return max(sgMax(start, mid, index*2, left, right), sgMax(mid+1, end, index*2+1, left, right))
}
// 두가지 세그먼트 트리 생성
sgMinInit(1, arr.count-1, 1)
sgMaxInit(1, arr.count-1, 1)
// 동작구현
for i in 0..<M {
let range = readLine()!.split(separator: " ").map{Int(String($0))!}
print("\(sgMin(1, arr.count-1, 1, range[0], range[1])) \(sgMax(1, arr.count-1, 1, range[0], range[1]))")
}
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.
내가 푼 풀이
접근방법: 세그먼트 트리
구간합트리인 세그먼트 트리를 구현후, 해당 동작들을 구현하였다.
입력 및 출력은 Int64의 최소최대값이 된다. 그래서 더해도 이 범위를 넘지않으므로 따로 오버플로우에 대한 대응은 하지않았다.
다만 Int로 선언시 본인의 컴퓨터에따라 다른 최댓값과 최솟값을 가질수 있으므로 안전하게 Int64로 사용해도 된다.(본인은 Int사용)
원소의 값을 변경할때, 세그먼트 트리도 변경되지만 주어진 N개의 배열도 값을 수정해줘야 다음 값변경에도 적용이 되므로 꼭 수정해줘야한다.
import Foundation
// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2]
var arr = [0]
for i in 0..<N {
arr.append(Int(readLine()!)!)
}
// 세그먼트 트리 크기지정
var tree = Array(repeating: 0, count: arr.count * 4)
// 세그먼트 트리 생성함수
func sgInit(_ start: Int,_ end: Int,_ index: Int) -> Int{
if start == end {
tree[index] = arr[start]
return tree[index]
}
let mid = (start + end)/2
tree[index] = sgInit(start, mid, index*2) &+ sgInit(mid+1, end, index*2+1)
return tree[index]
}
// 세그먼트트리를 이용한 구간합 구하기
func sgSum(_ start: Int,_ end: Int,_ index: Int,_ left: Int,_ right: Int) -> Int {
if left > end || right < start { return 0 }
if start >= left && end <= right {
return tree[index]
}
let mid = (start+end)/2
return sgSum(start, mid, index*2, left, right) &+ sgSum(mid+1, end, index*2+1, left, right)
}
// 원소값 변경으로 세그먼트트리의 값 수정
func sgUpdate(_ start: Int,_ end: Int,_ index: Int,_ node: Int,_ value: Int) {
if start > node || end < node { return }
tree[index] += value
if start == end { return }
let mid = (start+end)/2
sgUpdate(start, mid, index*2, node, value)
sgUpdate(mid+1, end, index*2+1, node, value)
}
// 세그먼트 트리 만들기
sgInit(1, arr.count-1, 1)
// 동작 수행
for i in 0..<M+K {
let op = readLine()!.split(separator: " ").map{Int(String($0))!}
if op[0] == 1 {
// 세그먼트 트리의 값 수정해주고, 배열값도 수정해준다.
sgUpdate(1, arr.count-1, 1, op[1], op[2] - arr[op[1]])
arr[op[1]] = op[2]
} else if op[0] == 2 {
print(sgSum(1, arr.count-1, 1, op[1], op[2]))
}
}
예시의 deph는 2단계라 바로 루트노드를 출력하지만, 더 깊다면 재귀호출을 통해 해당 집합의 루트노드를 반환한다.
두개의 분리집합을 합치는연산 Union을 사용하면 다음 그림과 같다.
parent
1
1
1
1
1
1
index
1
2
3
4
5
6
Union(1,2): 원소 1이 속한 집합과 원소2가 속한집합을 합친다.
합치는과정은 해당 루트노드가 합치려는 집합의 루트노드로 연결만 해주면된다.
합쳐졌다면 원소2,4,6 또한 루트노드 1을 가리키게 된다.
Union-Find의 시간복잡도는 Union연산은 연결만 해주므로 O(1)이 들지만, Find연산은 트리의 depth 만큼 재귀호출을 하므로
최소 O(1)에서 최대 O(depth)가 걸리게 된다.
이를 코드로 구현해보자.
import Foundation
// Union-Find
// 분리집합을 저장할 배열 parent
// parent[i] = a : i의 부모노드는 a다.
var parent = Array(repeating: 0, count: 7)
// 처음 초기화할땐 자기 자신을 루트노드로 갖는다.
for i in 1...6 {
parent[i] = i
}
// 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
// 이때 합쳐진 집합의 루트노드는 x의 루트노드가 된다.
func union(_ x: Int, _ y: Int) {
var rootX = find(x)
var rootY = find(y)
parent[rootY] = rootX
}
// 원소 x의 루트노드를 반환한다. (재귀호출)
// 재귀호출은 트리의 depth만큼 실행된다.
func find(_ x: Int) -> Int {
if parent[x] == x { return x}
parent[x] = find(parent[x])
return parent[x]
}
초기에𝑛+1개의 집합{0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에𝑛,𝑚이 주어진다.𝑚은 입력으로 주어지는 연산의 개수이다. 다음𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은0𝑎𝑏의 형태로 입력이 주어진다. 이는𝑎가 포함되어 있는 집합과,𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은1𝑎𝑏의 형태로 입력이 주어진다. 이는𝑎와𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
출력
1로 시작하는 입력에 대해서𝑎와𝑏가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.
내가 푼 풀이
문제 자체는 어려워보이지 않았다
접근방법: Dictionary 자료구조 이용(실패)
- 딕셔너리를 이용하려고 했는데 알고보니 문제를 잘 이해하지 못하고 도전했다.
- 합집합을 한 결과가 해당 집합이 되는줄 알고, 예로 1과 3을 합집합연산하면 (1,3), (3,1)이 생기는줄 알았다.
접근방법: Union-Find
- 주어진문제에서 서로다른 원소들은 전체집합을 이루고, 합집합을 한다면 union으로 합쳐주고, 같은 원소인지 판단하려면
두개의 해당 원소들의 루트노드가 같은지 확인하면 됬다.
- 이번 기회에 Union-Find 알고리즘을 알게되었는데, 서로소 집합에대해 포함하는지 효율적으로 탐색할 수 있다고 알게되었다.
코드로 구현하면 다음과 같다.
import Foundation
// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0], m = input[1]
// Union-Find
// 처음의 원소는 자기 자신을 루트노드로 갖는다.
// parent[x] = a: x의 부모노드는 a다.
var parent = Array(repeating: 0, count: n+1)
for i in 1...n {
parent[i] = i
}
// 두개의 서로소집합을 합친다.
// 단순히 y의 루트노드가 x를 가리키면 된다.
// 이 문제에서는 연산의 크기가 크지않아서 따로 설정하지 않았지만, 이 알고리즘은 트리의 depth에 따라 연산속도가 달라진다.
// 그래서 합치는 과정에서 depth가 큰노드가 작은노드를 루트노드로 합치는 방향이 더 좋다.
func union(_ x: Int, _ y: Int) {
var rootX = find(x)
var rootY = find(y)
parent[rootY] = rootX
}
// 해당 원소의 루트노드를 찾을때까지 재귀호출
func find(_ x: Int) -> Int {
if parent[x] == x { return x}
parent[x] = find(parent[x])
return parent[x]
}
// 연산 실행
for i in 0..<m {
let op = readLine()!.split(separator: " ").map{Int(String($0))!}
// 합집합은 서로 합쳐준다.
if op[0] == 0 {
union(op[1], op[2])
} else {
// 두 원소가 같은 집합에 있다는것은 둘다 같은 루트노드를 가리킴을 의미한다.
let p1 = find(op[1])
let p2 = find(op[2])
print(p1 == p2 ? "YES" : "NO")
}
}
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
출력
첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.
내가 푼 풀이
- 주어진 탑의 마지막순서부터 첫번째 순서로 이동하며, 자신의 탑보다 높은 탑이 있다면 수신가능
- 수신가능한 탑의 인덱스들을 출력.
접근방법: 스택
- 이 문제는 이전에 풀었던 오큰수 문제와 유사하다.
- 스택을 이용해서 배열을 탐색할때, 스택의 top이 현재원소보다 작다면 스택에 넣어주고, 크다면 스택의 선입후출방식을 이용해 작은값들을 전부 빼준다.
- 수신가능한 탑이 존재하지 않으면 0
import Foundation
// 입력받기
let N = Int(readLine()!)!
var arr = Array(readLine()!.split(separator: " ").map{Int(String($0))!}.reversed())
var stack = [Int]()
var result = Array(repeating: 0, count: N)
// 배열 arr은 주어진 탑의 순서를 뒤집어놓았다.
// arr순회할때마다, 스택이 비어있거나 스택의 top이 현재 값보다 작다면 스택에 추가한다.
// 스택의 top보다 현재 주어진 값이 더 크다면 스택에 있는 모든 값들을 현재값들과 비교하여 pop한다.
for i in 0..<arr.count {
if stack.isEmpty {
stack.append(i)
continue
}
while !stack.isEmpty && arr[i] > arr[stack[stack.count - 1]] {
// 정답의 인덱스는 첫번째가 1이므로 i+1 (0은 수신불가표시하기위해)
result[stack.removeLast()] = i+1
}
stack.append(i)
}
// 배열 뒤집어놓은것을 다시 돌려놓고, 출력
for i in 0..<result.count {
if result[i] == 0 { continue }
result[i] = (N+1) - result[i]
}
print(Array(result.reversed()).map{String($0)}.joined(separator: " "))
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
내가 푼 풀이
- 큐를 구현하고, 위 동작들을 메서드로 구현해준다.
import Foundation
// 입력받기
let T = Int(readLine()!)!
for i in 0..<T {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var queue = [(idx: Int, ipt: Int)]()
var count = 0
for j in 0..<arr.count {
queue.append((idx: j, ipt: arr[j]))
}
// 궁금한 문서 뽑을때까지 반복
while true {
if isImportant(queue) {
count += 1
if pop(&queue).idx == M { break }
} else {
moveBack(&queue)
}
}
print(count)
}
// 첫번째원소가 중요도가 가장 높은지 파악
func isImportant(_ queue: [(idx: Int, ipt: Int)]) -> Bool {
guard let top = top(queue) else { return false }
var max = Int.min
for i in queue {
if i.ipt > max { max = i.ipt }
}
if max == top.ipt { return true } else { return false }
}
// 첫번째 원소 출력
func top(_ queue: [(idx: Int, ipt: Int)]) -> (idx: Int, ipt: Int)? {
if queue.isEmpty { return nil }
return queue[0]
}
// 첫번째 원소 Pop
func pop(_ queue: inout [(idx: Int, ipt: Int)]) -> (idx: Int, ipt: Int) {
var a = Array(queue.reversed())
let num = a.removeLast()
queue = Array(a.reversed())
return num
}
// 첫번째 원소 뒤로 이동
func moveBack(_ queue: inout [(idx: Int, ipt: Int)]) {
let num = pop(&queue)
queue.append(num)
}
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.
입력
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
내가 푼 풀이
접근방법: 이분탐색
이전에 두용액문제를 풀고왔더니 너무 쉽게 파악해버렸다
두 용액을 섞을땐 용액의수가 최대 10만이였는데 이 문제에선 최대 5000 이다.
단순히 두 용액을 고정하고 한 용액을 순회하며 섞어봐도 정답은 나오지만 5000^3 = 1250억번 연산이므로 시간초과가 무조건 뜰것이다.
그래서 두개의 용액을 고정하고 한 용액을 구할때 이분탐색을 이용했다.
시간복잡도는 O(N^2logN)으로 이문제에선 약 9700만번연산(1억보다 적다)으로 시간안에 풀어졌다.
이분탐색
용액을 섞었을때, 음수면 start인덱스가 mid+1 양수면 end인덱스가 mid-1 해주어 0과 가장 가깝게 만든다.
코드로 구현하면 다음과 같다.
import Foundation
// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var minSum = Int.max
var answer = [Int]()
// 이분탐색 사용을위해 정렬
arr.sort(by: <)
// 이분탐색
for i in 0..<N {
for j in i+1..<N {
// 두용액을 고정한다.
let first = arr[i]
let second = arr[j]
let sum = first + second
var s = j+1
var e = N-1
// 나머지 한용액을 이분탐색을 이용해 구해준다.
while s <= e {
let m = (s+e)/2
let total = sum + arr[m]
// 0이되면 바로 값 갱신 후 탈출
if total == 0 {
answer = [arr[i],arr[j],arr[m]]
minSum = total
break
}
// 합쳐진 용액이 음수면 나머지 용액을 더 큰수로, 양수면 더 작은수로
if total < 0 {
s = m+1
} else {
e = m-1
}
// 최솟값이 나오면 항상 값을 갱신해준다.
if minSum > abs(total) {
minSum = abs(total)
answer = [arr[i],arr[j],arr[m]]
}
}
}
}
print("\(answer[0]) \(answer[1]) \(answer[2])")
