BOJ) 최솟값과 최댓값 (2357 번)

최솟값과 최댓값

2357번: 최솟값과 최댓값

 

 

앞서 포스팅한 세그먼트 트리를 활용하는 문제다.

위의 문제와 차이점이라면 구간 합을 구하는 대신, 최솟값과 최댓값을 저장한다는 점이다.

또한, 이 문제에서는 세그먼트 트리의 크기를 직접 구해서 초기화해줬다.

 

세그먼트 트리 초기화

 

private static class SegmentTree {
        int[] minTree, maxTree, numArr;
        private int size;

        public SegmentTree(int n, int[] numArr) {
            this.size = 1 << ((int) Math.ceil(Math.log(n)/Math.log(2)) +1);
            this.minTree = new int[this.size];
            this.maxTree = new int[this.size];
            this.numArr = numArr;
        }

        public void init(int node, int start, int end) {
            this.minInit(node, start, end);
            this.maxInit(node, start, end);
        }

        private int minInit(int node, int start, int end) {
            if(start == end) {
                return this.minTree[node] = this.numArr[start];
            }
            int mid = (start+end)/2;
            return this.minTree[node] = Math.min(this.minInit(node*2, start, mid), this.minInit(node*2+1, mid+1, end));
        }

        private int maxInit(int node, int start, int end) {
            if(start == end) {
                return this.maxTree[node] = this.numArr[start];
            }
            int mid = (start+end)/2;
            return this.maxTree[node] = Math.max(this.maxInit(node*2, start, mid), this.maxInit(node*2+1, mid+1, end));
        }
}

 

자바에서는 log2에 대한 연산을 지원하지 않기 때문에, 로그의 연산 규칙에 따라 log2 n을 직접 취해줬다.

Math.ceil은 소수점 올림 식이다.

init하는 부분도 처음에는 min과 max를 한번에 해주었었는데, 로직을 나누는게 더 깔끔해보여서 나눴다.

리프 노드가 아닌 노드에는 배열의 값을 그대로 저장해주고, 리프 노드에는 각각 구간의 최솟값과 최댓값을 저장해주었다.

 

 

최솟값 & 최댓값 찾기

 

public int findMinValue(int node, int start, int end, int left, int right) {
	if(left > end || right < start) { // out of range
		return Integer.MAX_VALUE;
	}
	if(left <= start && right >= end) { // found value
		return this.minTree[node];
	}
	int mid = (start+end)/2;
	return Math.min(this.findMinValue(node*2, start, mid, left, right), this.findMinValue(node*2+1, mid +1, end, left, right));
}

public int findMaxValue(int node, int start, int end, int left, int right) {
	if(left > end || right < start) { // out of range
		return Integer.MIN_VALUE;
	}
	if(left <= start && right >= end) { // found value
		return this.maxTree[node];
	}
	int mid = (start+end)/2;
	return Math.max(this.findMaxValue(node*2, start, mid, left, right), this.findMaxValue(node*2+1, mid +1, end, left, right));
}

 

생각보다 간단하다.

앞선 문제에서 합을 구하는 메소드를 이용해서, 각각 최솟값과 최댓값을 찾아 반환하도록 만들었다.

 

1) [left,right]와 [start,end]가 겹치지 않는 경우 ( 담당하는 구간이 다른 경우 ~> out of range)
2) [left,right]가 [start,end]를 완전히 포함하는 경우( 리프 노드가 node가 담당하는 구간 상위에 있는 경우 )
3) [start,end]가 [left,right]를 완전히 포함하는 경우 ( 리프 노드보다 담당하는 구간이 더 큰 경우 )
4) [left,right]와 [start,end]가 겹쳐져 있는 경우 (1, 2, 3 제외한 나머지 경우)

1번)
if (left > end || right < start) 로 나타낼 수 있다.
이 경우에는 구간이 겹치지 않기 때문에, 탐색을 이어나갈 필요가 없다.

2번)
if (left <= start && end <= right)로 나타낼 수 있다.
구해야하는 최소/최대의 범위는 [left,right]인데, [start,end]는 그 범위에 모두 포함되고, 그 node의 자식도 모두 포함되기 때문에 계속 호출을 하는 것은 비효율적이다.

3번 & 4번)
왼쪽 자식과 오른쪽 자식을 루트로 하는 트리에서 다시 탐색을 해야한다.

 

위의 규칙에 따라, 최대 최솟값을 비교하며 리턴해주었다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MinAndMax_2357 {
    final static String NEW_LINE = "\n", SPACE = " ";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] numArr = new int[n];
        for(int i=0; i<n; i++) {
            numArr[i] = Integer.parseInt(br.readLine());
        }

        int[][] commandArr = new int[m][2];
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            commandArr[i][0] = Integer.parseInt(st.nextToken());
            commandArr[i][1] = Integer.parseInt(st.nextToken());
        }
        br.close();

        solution(n, numArr, commandArr);
    }

    private static void solution(int n, int[] numArr, int[][] commandArr) {
        SegmentTree segmentTree = new SegmentTree(n, numArr);
        segmentTree.init(1, 0, n-1);
        StringBuilder sb = new StringBuilder();
        for(int[] commandInfo : commandArr) {
            int left = commandInfo[0] -1, right = commandInfo[1] -1;
            sb.append(segmentTree.findMinValue(1,0,n-1,left,right)).append(SPACE);
            sb.append(segmentTree.findMaxValue(1,0,n-1,left,right)).append(NEW_LINE);
        }
        System.out.println(sb.toString());
    }

    private static class SegmentTree {
        int[] minTree, maxTree, numArr;
        private int size;

        public SegmentTree(int n, int[] numArr) {
            this.size = 1 << ((int) Math.ceil(Math.log(n)/Math.log(2)) +1);
            this.minTree = new int[this.size];
            this.maxTree = new int[this.size];
            this.numArr = numArr;
        }

        public void init(int node, int start, int end) {
            this.minInit(node, start, end);
            this.maxInit(node, start, end);
        }

        private int minInit(int node, int start, int end) {
            if(start == end) {
                return this.minTree[node] = this.numArr[start];
            }
            int mid = (start+end)/2;
            return this.minTree[node] = Math.min(this.minInit(node*2, start, mid), this.minInit(node*2+1, mid+1, end));
        }

        private int maxInit(int node, int start, int end) {
            if(start == end) {
                return this.maxTree[node] = this.numArr[start];
            }
            int mid = (start+end)/2;
            return this.maxTree[node] = Math.max(this.maxInit(node*2, start, mid), this.maxInit(node*2+1, mid+1, end));
        }

        public int findMinValue(int node, int start, int end, int left, int right) {
            if(left > end || right < start) { // out of range
                return Integer.MAX_VALUE;
            }
            if(left <= start && right >= end) { // found value
                return this.minTree[node];
            }
            int mid = (start+end)/2;
            return Math.min(this.findMinValue(node*2, start, mid, left, right), this.findMinValue(node*2+1, mid +1, end, left, right));
        }

        public int findMaxValue(int node, int start, int end, int left, int right) {
            if(left > end || right < start) { // out of range
                return Integer.MIN_VALUE;
            }
            if(left <= start && right >= end) { // found value
                return this.maxTree[node];
            }
            int mid = (start+end)/2;
            return Math.max(this.findMaxValue(node*2, start, mid, left, right), this.findMaxValue(node*2+1, mid +1, end, left, right));
        }
    }
}