[Codeforces 1138C] Skyscrapers

[Codeforces 1138C] Skyscrapers

문제 설명 :

(n x m)크기의 행렬이 주어진다. 이 행렬에서 각각의 원소는 문제에서 정의한 연산에 의해서 어떤 값으로 바꿀 수 있다. 그 연산이란 어떤 원소와 그 원소가 속한 열과 행에 있는 모든 원소와 상대적인 크기(크거나, 작거나, 같거나)를 매겨서 이 관계가 유지되는 한에서 원소의 값을 조절할 수 있다. 그래서 이 과정을 거치면서 각 행과 열에 포함된 원소의 값 중에서 가장 큰 값이 최소가 되도록 만드는 문제이다.

풀이 : 

각 행과 열에 포함된 원소의 값중에서 최대값이 최소가 되도록 만들어야 하므로, 각 값들 간의 차이는 1이 되도록 해야 한다. 그러면서 어떤 원소의 값의 최소를 구하기 위해서는 그 값보다 작은 원소의 개수가 몇 개인지 카운트해야 한다. 만약 그 개수가 3개라면 필연적으로 어떤 원소가 가질 수 있는 최소값은 4가 된다. 4보다 작은 원소로는 1,2,3이 가능하며 3이하는 3개보다 작을 수 밖에 없기 때문이다. 그런데 문제에서는 어떤 원소의 최소값이 아닌, 그 원소가 포함된 열과 행에 속한 모든 원소의 값들의 최대값 중에서 최소값을 구해야한다. 따라서 그 최대값을 구하기 위해서는 다시 어떤 원소보다 값이 큰 원소의 개수가 몇 개인지를 다시 카운트해야 한다. 아래 첨부한 코드의 83~85번 째 줄에 나와있듯이 행과 열에서 작은 값의 개수를 각각 L_col,L_row라 하고 큰 값의 개수를 같은 원리로 G_col,G_row라고 두었다. 그래서 최종 답은 두 L중에서 큰 값과 G중에서 큰 값을 더한 값에 1을 더한 것이 답이 된다. 그렇다면 이 논리를 수행하는데 걸리는 시간은 어떨까. 일단 행렬의 모든 원소에 대해서 수행해야 하므로 O(N * M * ?)이 된다. N,M의 크기가 최대 1000이므로 ?의 시간복잡도로 O(N)은 허용되지 않는다. 내가 고민에 빠진 지점이 여기였다. 어떻게 하면 O(N)보다 빠르게 특정 값보다 작거나 큰 원소의 개수를 구할 수 있을지 말이다. 여기서 힌트는 '전처리'이다. 어차피 같은 열, 행에 속하는 원소들은 동일한 전처리를 참조하게 된다. 바로 '이분 탐색'을 이용하면 된다. 예를 들어 2,3,4,5 라는 배열에서 4보다 작은 원소의 개수, 4보다 큰 원소의 개수를 찾는다고 해보자. 이를 이진 탐색을 이용하면 O(logN)만에 할 수 있다. 그 방법은 이진 탐색을 하며 4를 찾으면서 그것의 인덱스가 얼마인지를 구하면 된다. 위 배열에서 4의 인덱스는 2이므로(0-base)  그보다 작은 원소의 개수는 곧 2개가 되고 큰 원소의 개수는 전체 n개 중 4의 인덱스(2)를 빼고 다시 1은 빼면 4-2-1=1이 된다. 이런 원리로 구하면 된다.

그 외 주의할 점 : 

1. 이진 탐색 알고리즘에서 left값과 right값의 경계 값에서 -1과 +1을 해주어야 한다.

2. 벡터의 unique연산은 바로 인접한 원소에 대해서만 중복된 원소를 지워주므로 사전에 정렬을 해주든가 전처리가 필요하다. 그리고 unique를 수행한 결과에서 중복된 원소를 걸러냈다고 해서 벡터의 크기가 줄어들지는 않는다. 다만 unique함수의 반환값으로 중복되지 않은 원소의 마지막 iterator를 반환하므로 iterator~vector.end()는 중복된 구간이다. 이 구간이 필요 없다면 vector.erase(iterator,vector.end())로 지워버리자.(밑의 코드 72,78번 째 줄 참고)

배운 점 : 

행과 열에서 큰 값의 개수와 작은 값의 개수를 구해야 한다는 것까지는 구상을 했는데 어떻게 O(N)보다 빠르게 구할 수 있는지가 관건이었다. 정렬을 한 뒤 이진 탐색을 이용해서 인덱스로 계산을 하면 O(logN)만에 개수를 구할 수 있다는 점을 배워간 문제였다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 1009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
vector<int> col[SIZE],row[SIZE];
int arr[SIZE][SIZE];
 
int bin_search(vector<int> &v,int val){
    int l=-1,r=v.size(),mid;
 
    while(l+1<r){
        mid=(l+r)/2;
 
        if(v[mid]==val) return mid;
        else if(v[mid]>val) r=mid;
        else l=mid;
    }
}
 
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            scanf("%d",&arr[i][j]);
            col[i].push_back(arr[i][j]);
            row[j].push_back(arr[i][j]);
        }
    }
 
    for(int i=1 ; i<=n ; i++){
        sort(col[i].begin(),col[i].end());
        auto it=unique(col[i].begin(),col[i].end());
        col[i].erase(it,col[i].end());
    }
 
    for(int i=1 ; i<=m ; i++){
        sort(row[i].begin(),row[i].end());
        auto it=unique(row[i].begin(),row[i].end());
        row[i].erase(it,row[i].end());     
    }
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            int L_col=bin_search(col[i],arr[i][j]),G_col=col[i].size()-L_col-1;
            int L_row=bin_search(row[j],arr[i][j]),G_row=row[j].size()-L_row-1;
            int ans=max(L_col,L_row)+max(G_col,G_row)+1;
            printf("%d ",ans);
        }
        printf("\n");
    }
 
    return 0;
}