[백준 2357번] 최솟값과 최댓값 - JAVA, Python

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

2357번: 최솟값과 최댓값

풀이

사용한 알고리즘 : 세그먼트 트리

 

풀이 전략

그림 출처:  http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220791986409

세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조로 위와같은 구조를 가진다.

 

최댓값을 저장하는 트리 초기 설정 코드

static int max_init(int arr[], int node, int nodeLeft, int nodeRight){
    if(nodeLeft==nodeRight){
        return max_tree[node]=arr[nodeLeft];
    }

    int mid=nodeLeft+(nodeRight-nodeLeft)/2;
    return max_tree[node]=Math.max(max_init(arr,node*2,nodeLeft,mid),
            max_init(arr,node*2+1,mid+1,nodeRight));
}

arr는 입력 배열, node는 현재 노드의 인덱스 번호, nodeLeft는 왼쪽 노드의 인덱스 번호, nodeRight는 오른쪽 노드의 인덱스 번호이다.

nodeLeft=rightLeft 는 리프 노드를 뜻하므로, 트리의 해당 인덱스에 원래 입력했었던 배열의 원소를 저장한다. 그리고 점차 노드의 높이를 올려가며 최댓값을 저장해가는 함수이다.

 

예로 arr = [1,2,3,4,5,6,7,8] 이었다면 tree[3]=arr[3-1]=3 이 저장되는 것이다.

 

특정 범위 내에서 최댓값을 찾는 코드

static int max_query(int start, int end, int node, int nodeLeft, int nodeRight){
    if(start>nodeRight || end<nodeLeft){
        return -1;
    }

    if(start<=nodeLeft && end>=nodeRight){
        return max_tree[node];
    }

    int mid=nodeLeft+(nodeRight-nodeLeft)/2;
    return Math.max(max_query(start,end,node*2,nodeLeft,mid),
            max_query(start,end,node*2+1,mid+1,nodeRight));
}

범위 내에 없으면 비교할 필요가 없으므로, 최댓값이 되지 못하도록 트리의 해당 노드 값을 -1로 만든다.그리고 탐색하며 방문한 노드가 범위 내에 완전히 들어가 있으면 현재 노드의 값을 반환(그 노드가 관할하는 영역에서의 최댓값을 가지므로)한다.

위 상황 둘다 아니면 탐색을 이어간다.

 

제출코드

1. JAVA

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static int max_tree[];
    static int min_tree[];
    static int max_init(int arr[], int node, int nodeLeft, int nodeRight){
        if(nodeLeft==nodeRight){
            return max_tree[node]=arr[nodeLeft];
        }

        int mid=nodeLeft+(nodeRight-nodeLeft)/2;
        return max_tree[node]=Math.max(max_init(arr,node*2,nodeLeft,mid),
                max_init(arr,node*2+1,mid+1,nodeRight));
    }

    static int min_init(int arr[], int node, int nodeLeft, int nodeRight){
        if(nodeLeft==nodeRight){
            return min_tree[node]=arr[nodeLeft];
        }

        int mid=nodeLeft+(nodeRight-nodeLeft)/2;
        return min_tree[node]=Math.min(min_init(arr,node*2,nodeLeft,mid),
                min_init(arr,node*2+1,mid+1,nodeRight));
    }

    static int max_query(int start, int end, int node, int nodeLeft, int nodeRight){
        if(start>nodeRight || end<nodeLeft){
            return -1;
        }

        if(start<=nodeLeft && end>=nodeRight){
            return max_tree[node];
        }

        int mid=nodeLeft+(nodeRight-nodeLeft)/2;
        return Math.max(max_query(start,end,node*2,nodeLeft,mid),
                max_query(start,end,node*2+1,mid+1,nodeRight));
    }

    static int min_query(int start, int end, int node, int nodeLeft, int nodeRight){
        if(start>nodeRight || end<nodeLeft){
            return 1000000001;
        }

        if(start<=nodeLeft && end>=nodeRight){
            return min_tree[node];
        }

        int mid=nodeLeft+(nodeRight-nodeLeft)/2;
        return Math.min(min_query(start,end,node*2,nodeLeft,mid),
                min_query(start,end,node*2+1,mid+1,nodeRight));
    }

    public static void main(String args[]) throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        int arr[] = new int[N];
        for(int i=0;i<N;++i){
            arr[i]=Integer.parseInt(br.readLine());
        }
        max_tree=new int[4*N];
        min_tree=new int[4*N];
        min_init(arr,1,0,N-1);
        max_init(arr,1,0,N-1);

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            System.out.println(min_query(a-1,b-1,1,0,N-1)+" "
                    +max_query(a-1,b-1,1,0,N-1));
        }
    }
}

 

2. Python

import sys

input=sys.stdin.readline

def max_merge(val1,val2):
    return max(val1,val2)

def min_merge(val1,val2):
    return min(val1,val2)

def max_build(arr,node,leftNode,rightNode):
    if leftNode==rightNode:
        max_tree[node] = arr[leftNode]
        return max_tree[node]

    mid=leftNode+(rightNode-leftNode)//2
    leftNode=max_build(arr,node*2,leftNode,mid)
    rightNode=max_build(arr,node*2+1,mid+1,rightNode)
    max_tree[node]=max_merge(leftNode,rightNode)
    return max_tree[node]

def min_build(arr,node,leftNode,rightNode):
    if leftNode==rightNode:
        min_tree[node] = arr[leftNode]
        return min_tree[node]

    mid=leftNode+(rightNode-leftNode)//2
    leftNode=min_build(arr,node*2,leftNode,mid)
    rightNode=min_build(arr,node*2+1,mid+1,rightNode)
    min_tree[node]=min_merge(leftNode,rightNode)
    return min_tree[node]

def max_request(start,end,node,leftNode,rightNode):
    if end<leftNode or start>rightNode:
        return -int(1e9)

    if start<=leftNode and end>=rightNode:
        return max_tree[node]

    mid=leftNode+(rightNode-leftNode)//2
    leftNode=max_request(start,end,node*2,leftNode,mid)
    rightNode=max_request(start,end,node*2+1,mid+1,rightNode)
    return max(leftNode,rightNode)

def min_request(start,end,node,leftNode,rightNode):
    if end<leftNode or start>rightNode:
        return int(1e9)

    if start<=leftNode and end>=rightNode:
        return min_tree[node]

    mid=leftNode+(rightNode-leftNode)//2
    leftNode=min_request(start,end,node*2,leftNode,mid)
    rightNode=min_request(start,end,node*2+1,mid+1,rightNode)
    return min(leftNode,rightNode)


n,m=map(int,input().split())

arr=[]
max_tree=[0]*(4*n)
min_tree=[int(1e9)]*(4*n)
for i in range(n):
    arr.append(int(input()))

max_build(arr,1,0,n-1)
min_build(arr,1,0,n-1)
for i in range(m):
    a,b=map(int,input().split())
    print(min_request(a-1,b-1,1,0,n-1),max_request(a-1,b-1,1,0,n-1))