문제 개요
크기가 N인 정수 배열이 주어졌을 때, 변수 L과 R은 1부터 N 사이의 범위를 정의합니다(L ≥ 1, R ≤ N). 이 문제의 목표는 범위 [L, R] 안에 포함된 요소들 중 최솟값이 몇 번 등장하는지 그 개수를 구하는 것입니다.
해결 접근 방식
- 먼저 L부터 R까지 범위에 속한 요소들을 한 번 순회하면서 가장 작은 값을 찾습니다.
- 같은 범위를 다시 순회하면서 앞서 구한 최솟값과 동일한 요소가 나타날 때마다 카운트를 증가시킵니다.
구체적인 예제를 통해 살펴보겠습니다.
입력 − arr[] = { 1,2,3,0,3,2,0,1 }, N = 8, L = 2, R = 5
출력 − 범위 내 최솟값의 개수 − 1
설명 −
범위 L(2)부터 R(5)에 해당하는 요소는 arr[1]부터 arr[4]까지로, { 2,3,0,3 }입니다. 최솟값은 0이며, 0은 1번 등장합니다.
입력 − arr[] = { 1,2,3,0,3,2,0,1 }, N = 8, L = 3, R = 8
출력 − 범위 내 최솟값의 개수 − 2
설명 −
범위 L(3)부터 R(8)에 해당하는 요소는 arr[2]부터 arr[7]까지로, { 3,0,3,2,0,1 }입니다. 최솟값은 0이며, 0은 2번 등장합니다.
프로그램에 적용한 접근 방식
- 임의의 값으로 초기화된 정수 배열 arr[]를 준비합니다.
- 정수 L과 R은 배열 arr[] 내부의 탐색 범위를 나타내며, count는 해당 범위 내 최솟값의 개수를 저장합니다.
- 함수 countSmallest(int arr[], int n, int l, int r)는 배열, 배열 길이, L, R을 입력으로 받아 범위 내 최솟값의 개수를 반환합니다.
- smallest를 범위의 왼쪽 끝 요소인 arr[l]로 초기화하고, count는 0으로 초기화합니다.
- 만약 l < 0이고 r >= n이라면 유효하지 않은 범위이므로 0을 반환합니다.
- 인덱스 l-1부터 r-1까지 배열을 순회하면서 arr[i] < smallest이면 smallest를 갱신합니다.
- 다시 l-1부터 r-1까지 순회하면서 arr[i] == smallest이면 count를 증가시킵니다.
- count를 결과값으로 반환합니다.
- main 함수 안에서 count에 저장된 결과를 화면에 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 주어진 범위에서 최솟값의 개수를 구하는 함수
int countSmallest(int arr[],int n,int l, int r){
int smallest=arr[l];
int count=0;
if(l<0 && r>=n)
return 0;
for(int i=l-1;i<r;i++){
if(arr[i]<=smallest){
smallest=arr[i];
}
}
for(int i=l-1;i<r;i++){
if(arr[i]==smallest){
++count;
}
}
return count;
}
int main(){
int arr[] = { 3,2,1,1,2,3 };
int n = 6;
int L,R;
int count=0;
L=1,R=5;
count=countSmallest(arr,n,L,R);
cout<<endl<<"Count of number of smallest in given range:"<<count;
L=3,R=4;
count=countSmallest(arr,n,L,R);
cout<<endl<<"Count of number of smallest in given range:"<<count;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of number of smallest in given range:2
Count of number of smallest in given range:2