BOJ-2357 최솟값과 최댓값 Swift

문제

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]))")
}