[BOJ] 백준 10868번 : 최솟값 (JAVA)

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

 

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 

 

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

 

 

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

 

 

풀이

세그먼트 트리로 풀 수 있는 문제였습니다. '2357번 최솟값과 최댓값' 문제보다 비슷하지만, 더 쉬운 문제였습니다.

위 문제가 궁금하신 분은 아래 링크를 참조하시길 바랍니다.

 

 

[BOJ] 백준 2357번 : 최솟값과 최댓값 (JAVA)

 

 

세그먼트 트리를 처음 배울 때, init이라는 함수에서 구간합을 구하고, update와 sum 등의 메소드를 통해서 구간 내의 값을 변경하거나 특정 구간합을 구하는 과정을 취했습니다.

 

이번에는 단순히 특정 구간 내에 최솟값만 판별하면 되기때문에 init 함수에서 구간 별로 최솟값을 저장하고, find 함수에서는 서 특정 구간 내에 최솟값을 반환하도록 설계하면 됩니다.

 

위 2개의 함수의 형태도 처음 배울 때 구간합 코드와도 상당히 유사하기때문에 어렵지 않게 풀 수 있으실 듯 합니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.