2357번 : 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int arr[] = new int[n];
        SegmentTree segmentTree = new SegmentTree(n);

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        segmentTree.minTree(arr, 1, 0, n-1);
        segmentTree.maxTree(arr, 1, 0, n-1);
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            
            //최소값, 최대값 초기화
            segmentTree.min = Integer.MAX_VALUE;
            segmentTree.max = Integer.MIN_VALUE;
            
            //범위에 맞는 최소값 찾기
            segmentTree.query(1,0,n-1,left-1, right-1,0);
            //범위에 맞는 최대값 찾기
            segmentTree.query(1,0,n-1,left-1, right-1,1);
            sb.append(segmentTree.min + " " + segmentTree.max + "\n");
        }
        bw.write(sb+""); bw.flush();
    }
}
class SegmentTree {
    int tree[][];
    int treeSize;
    int min,max;
    public SegmentTree(int size) {
        int h = (int) Math.ceil(Math.log(size)/ Math.log(2));
        treeSize = (int)Math.pow(2,h+1);
        tree = new int[treeSize][2];
    }

    public int minTree(int arr[], int node, int start, int end) {
        if(start == end) {
            return tree[node][0] = tree[node][1] = arr[start];
        }
        return tree[node][0] = Math.min(minTree(arr, node*2, start, (start+end)/2),
                minTree(arr, node*2+1, (start+end)/2+1, end));
    }
    public int maxTree(int arr[], int node, int start, int end) {
        if(start == end) {
            return tree[node][0] = tree[node][1] = arr[start];
        }
        return tree[node][1] = Math.max(maxTree(arr, node*2, start, (start+end)/2),
                maxTree(arr, node*2+1, (start+end)/2+1, end));
    }

	//범위에 해당하는 최소값 또는 최대값 찾는 메서드
    public void query(int node, int start, int end, int left, int right, int type) {
        if(left>end || right<start) return;
        else if (left<=start && end<=right) {
            if(type==0) min = Math.min(min, tree[node][0]); //최소값
            else max = Math.max(max, tree[node][1]); //최대값
            return;
        }
        query(node*2, start, (start+end)/2, left, right, type);
        query(node*2+1, (start+end)/2+1, end, left, right, type);
    }
}

 

 

해결방법

이 문제는 세그먼트 트리를 사용해서 풀어야 정답이 나오는 문제인데 세그먼트 트리를 공부한 적이 없어서 공부를 하고 문제를 풀어보았다. 테스트 케이스는 잘 돌아가지만 시간초과가 나왔다. 입력받은 범위마다 minTree(), maxTree() 한것이 시간초과의 원인이라고 생각하여 minTree(), maxTree()를 전체 범위로 1번 수행하고 입력받은 범위에 해당하는 최솟값과 최댓값을 찾아야하는데 이를 찾는 코드(query())를 구현하지 못하여서 다른 사람의 코드를 보고 문제를 해결하였다.

 

세그먼트 트리 공부

 

참고한 다른 사람 풀이