[C++/탐색] 정렬된 2차원 배열에서 탐색하기
2023. 3. 30. 13:55ㆍC++
- 입력 : 첫 줄에 n (n = 1, 2 4 8 16, 32, 64, 128, 256, 512, 1024)과 정수 k가 주어지고, 다음 줄부터 각 행의 n개의 값이 차례로 주어진다.
- 특이하게 각 행의 값들과 각 열의 값들이 오름차순으로 정렬되어 주어진다.
- 출력 : 배열에 있는 값 중에서 k 값이 (i, j)에 있다면 i j를 차례로 출력하고 없다면 -1을 출력한다. (행과 열은 모두 0부터 시작한다.) 단, k 값이 두 개 이상 있다면 , 사전 순서로 가장 작은 (i, j)값을 출력한다.
- 사전 순서는 (a, b), (c, d) 두 위치에 대한 사전 순서는 a < c이면 (a,b)가 앞서는 것이고, a==c)인 경우에는 b와 d중에서 작은 값을 갖는 것이 앞서는 것이다.
- 첫 번째 샘플 입력에서 -4가 (1,3),(2,1),(3,0) 모두 세 곳에 등장한다. 사전 순서로 따지면 행 번호가 갖 ㅇ작은 (1,3)이 가장 앞서기에 (1,3)을 출력하면 된다.
정렬된 배열에서 값 찾기는 Binary_search 를 이용하면 된다. 좌,우 끝 인덱스를 기준으로 중앙 인덱스를 정하고 중앙인덱스와 찾으려는 값과 비교하여 상황에 따라서 출발점과 끝점을 이동시켜 탐색하는 과정이다. 이는 한 줄을 모두 탐색하는데 거리는 시간 O(n)보다 O(logn)으로 시간복잡도 면에서 성능이 뛰어나다.
문제를 해결하면서 각 행마다 binary_search를 적용하여 찾으려는 값과 동일한 인덱스를 추출하고 각 인덱스를 사전순으로 나열해 정답을 출력하는 방식으로 하였다.
전체 소스코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1025;
int arr[MAX][MAX];
int n,k;
int b_search(int idx,const long long find_num)
{
int s = 0;
int e = n-1;
while(s<=e)
{
if(arr[idx][s]==find_num)
return s;
if(arr[idx][e]==find_num)
return e;
int m = (s+e)/2;
if(arr[idx][m]==find_num)
return m;
else if(arr[idx][m]>find_num)
e = m-1;
else if(arr[idx][m]<find_num)
s = m+1;
}
return 100002;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>arr[i][j];
}
}
int x=100002,y=100002;
for(int i=0;i<n;i++)
{
int temp = b_search(i,k);
if(temp!=100002)
{
if(i<y)
{
y = i;
x = temp;
}
}
}
if(x==100002&&y==100002)
cout<<-1<<endl;
else
cout<<y<<" "<<x<<endl;
return 0;
}
/*
binary_search를 이용하여 탐색하였습니다. 각 행마다 binary_search로 탐색하여
(y,x) y가 작은 값을 먼저 찾고
만약 같은 행에 찾는 값이 있다면 x값이 더 작은 값을 출력하도록 하였습니다.
binary_serach는 log n의 수행시간을 가지고 행의 갯수n만큼 수행하니
O(nlogn) 수행시간으로 해결하였습니다,
*/
'C++' 카테고리의 다른 글
[C++/BackTracking/백준] 9663번 N-Queen (0) | 2023.08.24 |
---|---|
[C++/BackTracking/백준] 15649번 N과 M (1) (0) | 2023.08.22 |
[C++/배열,스캔] 오르락 내리락 (0) | 2023.03.17 |
[C++/백준] 2477번 참외밭 (0) | 2023.02.16 |
비트마스킹 (백준 11723번 집합) (0) | 2022.11.11 |