HS_development_log

백준 2357번 - 최솟값과 최댓값 / Java 본문

Algorithm-백준/세그먼트 트리

백준 2357번 - 최솟값과 최댓값 / Java

DevHyeonseong 2020. 1. 14. 19:29
반응형

문제

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

 

2357번: 최솟값과 최댓값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을

www.acmicpc.net

세그먼트 트리에 대한 이론을 공부하고 실전 문제에 적용하기위해 풀어본 문제.

문제 정답률이 약 48%로 세그먼트 트리에 대한 개념만 있다면 풀 수 있는 어렵지 않은 문제였다.

 

알고리즘

  1. 각 구간마다의 최솟값을 저장하는 세그먼트 트리를 만든다. 이때 구간에 대해 재귀적으로 트리를 구현할 수 있다.

  2. 각 구간마다의 최댓값을 저장하는 세그먼트 트리를 만든다. 방법은 1과같다.

  3. 1 과 2에서 만든 세그먼트 트리에서 테스트케이스에 해당하는 구간의 값을 가져온다

  4. 답을 순서대로 출력한다

소스코드 및 설명

 

1번 알고리즘

1
2
3
4
5
6
7
    public int minInit(int start, int end, int node) {
        if(start == end) {
            return minTree[node] = arr[start];
        }
        int mid = (start+end)/2;
        return minTree[node] = (int)Math.min(minInit(start, mid, node*2), minInit(mid+1,end, node*2+1));
    }
 cs

 

재귀적으로 수행해 내려가면서 각 구간에 대한 최솟값만 트리에 저장한다.

 

2번 알고리즘

재귀적으로 수행해 내려가면서 각 구간에 대한 최댓값만 트리에 저장한다

1
2
3
4
5
6
7
    public int maxInit(int start, int end, int node) {
        if(start == end) {
            return maxTree[node] = arr[start];
        }
        int mid = (start+end)/2;
        return maxTree[node] = (int)Math.max(maxInit(start, mid, node*2), maxInit(mid+1,end, node*2+1));
    }
 cs

 

3번 알고리즘 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    public int minFind(int start, int end, int node, int left, int right) {
        if(left>end || right< start) {
            return Integer.MAX_VALUE;
        }
        if(left <=start && end <=right) {
            return minTree[node];
        }
        int mid = (start+end)/2;
        return (int)Math.min(minFind(start, mid, node*2, left, right), minFind(mid+1, end, node*2+1, left, right));
    }
    public int maxFind(int start, int end, int node, int left, int right) {
        if(left>end || right< start) {
            return Integer.MIN_VALUE;
        }
        if(left <=start && end <=right) {
            return maxTree[node];
        }
        int mid = (start+end)/2;
        return (int)Math.max(maxFind(start, mid, node*2, left, right), maxFind(mid+1, end, node*2+1, left, right));
    }
    
 cs

최솟값, 최대값 트리에서 구간에 해당하는 값을 위와 마찬가지로 재귀적으로 찾는다.

 

4번 알고리즘 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    public static void main(String[] args) {
        SegmentTree st = new SegmentTree();
        st.minInit(0, st.n-1, 1);
        st.maxInit(0, st.n-1, 1);
        int answer[][] = new int[st.m][2];
        for(int i=0;i<st.m;i++) {
            answer[i] = new int[2];
            answer[i][0] = st.minFind(0, st.n-1, 1, st.test[i][0]-1, st.test[i][1]-1);
            answer[i][1] = st.maxFind(0, st.n-1, 1, st.test[i][0]-1, st.test[i][1]-1);    
        }
        for(int i =0;i<st.m;i++) {
            for(int j=0;j<answer[i].length;j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }
    }
 cs

메인 메소드에서 순서대로 구한 값을 출력한다.

 

전체 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.*;
public class BOJ2357 {
 
    public static void main(String[] args) {
        SegmentTree st = new SegmentTree();
        st.minInit(0, st.n-1, 1);
        st.maxInit(0, st.n-1, 1);
        int answer[][] = new int[st.m][2];
        for(int i=0;i<st.m;i++) {
            answer[i] = new int[2];
            answer[i][0] = st.minFind(0, st.n-1, 1, st.test[i][0]-1, st.test[i][1]-1);
            answer[i][1] = st.maxFind(0, st.n-1, 1, st.test[i][0]-1, st.test[i][1]-1);    
        }
        for(int i =0;i<st.m;i++) {
            for(int j=0;j<answer[i].length;j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }
    }
 
}
class SegmentTree{
    int n; // 수의 개수
    int m; // 테스트케이스
    int arr[]; // 세그먼트 트리를 만들 요소들
    int minTree[]; // 최솟값 세그먼트트리
    int maxTree[]; // 최댓값 세그먼트트리
    int test[][];
    public SegmentTree(){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = scan.nextInt();
        }
        test = new int[m][2];
        for(int i=0;i<m;i++) {
            test[i] = new int[2];
            test[i][0] = scan.nextInt();
            test[i][1] = scan.nextInt();
        }
        minTree = new int[n*4];
        maxTree = new int[n*4];
    }
    public int minInit(int start, int end, int node) {
        if(start == end) {
            return minTree[node] = arr[start];
        }
        int mid = (start+end)/2;
        return minTree[node] = (int)Math.min(minInit(start, mid, node*2), minInit(mid+1,end, node*2+1));
    }
    public int minFind(int start, int end, int node, int left, int right) {
        if(left>end || right< start) {
            return Integer.MAX_VALUE;
        }
        if(left <=start && end <=right) {
            return minTree[node];
        }
        int mid = (start+end)/2;
        return (int)Math.min(minFind(start, mid, node*2, left, right), minFind(mid+1, end, node*2+1, left, right));
    }
    
    public int maxInit(int start, int end, int node) {
        if(start == end) {
            return maxTree[node] = arr[start];
        }
        int mid = (start+end)/2;
        return maxTree[node] = (int)Math.max(maxInit(start, mid, node*2), maxInit(mid+1,end, node*2+1));
    }
    public int maxFind(int start, int end, int node, int left, int right) {
        if(left>end || right< start) {
            return Integer.MIN_VALUE;
        }
        if(left <=start && end <=right) {
            return maxTree[node];
        }
        int mid = (start+end)/2;
        return (int)Math.max(maxFind(start, mid, node*2, left, right), maxFind(mid+1, end, node*2+1, left, right));
    }
}
cs

 

2차원 배열을 이용하여 최댓값, 최솟값을 한번의 세그먼트트리로 구하는 방법도 생각해봤다.

하지만 그렇게되면 메소드의 return형식이 int가 아니라 1차원배열, 즉 프리미티브타입이 아닌 레퍼런스 타입이 되야한다.

그러면 깊은복사를 해줘야하고, 그에따른 메모리낭비와 시간추가도 있을것 같아 위의 코드와 효율성이 비슷할 것같아서 시도하지않았다.

반응형