BOJ 17140, 이차원 배열과 연산

Source: BOJ 17140 이차원 배열과 연산

문제를 이해하면서 행연산, 열연산을 따로 처리하기가 까다로울 것이라 생각하여 배열을 돌려 오로지 R 연산을 하도록 만들었다. 따라서 transArr란 함수를 만들어 행과 열을 뒤바꾸는 함수를 만들었고, C연산이 필요 할때는 transArr함수를 실행시키고 R연산을 할 수 있게끔 만들었다.

---

일단 문제를 정리해보면

1. 배열 A에 대해 R 또는 C연산을 수행.
2. 각각의 행(또는 열)에 각각의 수가 몇 번 나왔는지 저장
3. 저장된 값을 등장횟수가 많아지는 순으로 다시 정렬 후
4. 배열 A에 값을 update

PS LOGIC

1. transArr함수를 만들어 행/열 연산을 따로 만들지 않고 필요할 시 배열을 돌려서 연산하도록 만듬.
2. sortArr함수를 이용해 각각의 수의 등장횟수를 freqArr에 저장 후
3. freqArr의 idx 와 value 를 다시 vector v에 pair형으로 저장
4. v에 저장된 값들을 for-each문을 이용해 기존의 arr에 업데이트

---

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int arr[102][102];
int n = 3;
int m = 3;
int r, c, k;

void transArr(){
  int mx = max(n, m);
  for(int i=1; i<=mx; i++){
    for(int j=i+1; j<=mx; j++){
      swap(arr[i][j], arr[j][i]);
    }
  }
  swap(n, m);
}

void sortArr(int arr[]){
  int freqArr[102] = {};
  for(int i=1; i<=n; i++){
    if(!arr[i])continue;
    freqArr[arr[i]]++;
  }
  vector<pair<int, int>> v;
  for(int i=1; i<=100; i++){
    if(!freqArr[i])continue;
    v.push_back({freqArr[i], i});
  }
  sort(v.begin(), v.end());
  int j=0;
  for(auto c: v){
    arr[++j] = c.Y;
    arr[++j] = c.X;
  }
  n = max(n, j);
  fill(arr+j+1, arr+n+1, 0);
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>r>>c>>k;
  for(int i=1; i<=3; i++){
    for(int j=1; j<=3; j++){
      cin>>arr[i][j];
    }
  }
  int t = 0; 
  while( t<=100 && arr[r][c] != k){
    bool transposed = false;
    if(m<n){
      transArr();
      transposed = true;
    }
    for(int i=1; i<=m; i++){
      sortArr(arr[i]);
    }
    if(transposed){
      transArr();
    }
    t++;
  }
  cout<<(t > 100 ? -1 : t);
}