백준 1895 Filter

문제링크: https://www.acmicpc.net/problem/1895
난이도: 실버4
알고리즘: 브루트포스 알고리즘,정렬,슬라이딩 윈도우
문제 해결 idea: 가장 왼쪽위 좌표부터 33의 배열크기만큼 돌며 중앙값을 구하는 문제이다.
일단 행과 열의 기준좌표를 구하면 33만큼 탐색해야 하기 때문에 4차원 배열로 문제를 풀어야 겠다고 생각했다.
왜냐? 일단 행과 열로 주어지는 값의 범위가 40보다 작기때문에 4차원 for문으로 돌아도 시간초과가 나지 않을것이라 생각했다.
4중 for문을 돌며 각 좌표에 해당하는 픽셀값을 벡터에 저장한다.
벡터에 저장된 픽셀값이 9개가 될경우, sort를 하여 중앙값을 구하고, 각 행별 중앙값 계산을 한 열들의 픽셀값을 저장하기 위해 r_t라는 int형 벡터 변수를 선언하여 저장하도록 했다.
기준 좌표의 행기준 모든 열의 탐색이 끝났을경우 r_t에 저장된 열값을 이중벡터 tmp에 저장하여 중앙값 계산이 완료된 값을 저장하도록 했다.

처음 푼 풀이:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[41][41];
vector<vector<int>>tmp;

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    int r,c;
    int res=0;
    cin>>r>>c;
    
    
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>arr[i][j];
        }
    }
    int t;
    cin>>t;
   
   
    for(int i=0;i<r;i++){
        vector<int>r_t;
        for(int j=0;j<c;j++){
            vector<int>lis;
            for(int nx=i;(nx-i)<3;nx++){
                if(nx>=r){
                    break;
                }
                for(int ny=j;(ny-j)<3;ny++){
                    if(ny>=c){
                        break;
                    }
                    lis.push_back(arr[nx][ny]);
                    
                }
                
            }
            if(lis.size()==9){
                sort(lis.begin(), lis.end());
                r_t.push_back(lis[lis.size()/2]);
            }
          
        }
        if(!r_t.empty()){
            tmp.push_back(r_t);
        }
     
    }
    
    for(int i=0;i<tmp.size();i++){
        for(int j=0;j<tmp[i].size();j++){
            if(t<=tmp[i][j]){
                res++;
            }
        }
    }
    
    cout<<res<<"\n";
    
    return 0;
}

위에서 기준좌표에서 3*3배열 탐색시 배열의 크기를 넘어갈 경우 중앙값 계산을 하지 않도록 하기 위해
if문을 통해 기존 행과 열의 범위를 넘겼는지 확인하도록 했었는데, 작성하고 보니 코드가 너무 더러운거 같았다. 좀더 가독성 좋은 코드로 해결할 방법이 있을까? 고민하여 두번째로 코드를 수정해보았다.

두번째 코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[41][41];
vector<vector<int>>tmp;

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    int r,c;
    int res=0;
    cin>>r>>c;
    
    
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>arr[i][j];
        }
    }
    int t;
    cin>>t;
   
   
    for(int i=0;i+2<r;i++){
        vector<int>r_t;
        for(int j=0;j+2<c;j++){
            vector<int>lis;
            for(int nx=i;(nx-i)<3;nx++){

                for(int ny=j;(ny-j)<3;ny++){
                    lis.push_back(arr[nx][ny]);
                }
                
            }
            if(lis.size()==9){
                sort(lis.begin(), lis.end());
                r_t.push_back(lis[lis.size()/2]);
            }
          
        }
        if(!r_t.empty()){
            tmp.push_back(r_t);
        }
     
    }
    
    for(int i=0;i<tmp.size();i++){
        for(int j=0;j<tmp[i].size();j++){
            if(t<=tmp[i][j]){
                res++;
            }
        }
    }
    
    cout<<res<<"\n";
    
    return 0;
}

for문의 조건에 i+2<r , j+2<c로 변경하여 좀더 깔끔하게 작성할 수 있었다.