알고리즘||코딩테스트/백준
[백준 2357번] 최솟값과 최댓값 - JAVA, Python
째로스
2023. 7. 11. 14:37
https://www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
풀이
사용한 알고리즘 : 세그먼트 트리
풀이 전략
세그먼트 트리란 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조로 위와같은 구조를 가진다.
최댓값을 저장하는 트리 초기 설정 코드
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))
