백준 17140번: 이차원 배열과 연산 (C++)

문제 링크 : www.acmicpc.net/problem/17143

 

 

 구현, 시뮬레이션 문제이다. 

 

 

<전체적인 알고리즘>

1. 행이 열보다 크면 R 연산으로 모든 행마다 벡터로 저장을 해서 sorting함수로 넘겨준다.

   열이 행보다 크면 C 연산으로 모든 열마다 벡터로 저장을 해서 sorting 함수로 넘겨준다.

2. sorting 함수에서 sorting을 진행해준다.

   2-1. 벡터를 탐색하며 num_count배열에서 해당 숫자의 index의 값을 증가시켜줌(숫자 개수 구하는 거임)

   2-2  num_count를 탐색하며 벡터에  (숫자와 개수를) 쌍으로 넣어준다.

   2-3 넣으준 벡터를 sort 라이브러리로 문제 조건대로 정렬시켜줌 

3. sorting으로 정렬이 되면 그 뒤의 값들은 0으로 채워준다, row와 column 사이즈 갱신

4. 1,2,3, 반복

 

<sort>

sort라이브러리를 사용할 때 그냥 sort를 하면 안되고 compare함수를 구현해야 한다.

숫자의 개수가 다르다면 숫자의 개수가 커지는 순으로 정렬, 숫자의 개수가 같다면 숫자가 커지는 순으로 정렬을 한다.

 

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

#include<iostream> #include<vector> #include<algorithm>   using namespace std;   int buffer[102][102]; int num_count[102];   bool compare(pair<int, int> a, pair<int, int> b)  //수의 등장 횟수가 커지는 순으로,, {                                                  // 그러한 것이 여러가지면 수가 커지는 순으로 정렬     if (a.second != b.second)return a.second < b.second;     else return a.first < b.first; }   void sorting(vector<int> &v)   //조건대로 정렬 {     vector<pair<int, int>> tmp;           fill(&num_count[0], &num_count[101], 0);     for (int i = 0; i < v.size(); i++)  //map으로 숫자들 카운팅하기     {         int num = v[i];         if (num == 0)continue;         num_count[num]++;          //숫자index에 수 증가     }     for (int i = 1; i <= 100; i++)    //숫자와 개수 쌍으로 벡터에 저장     {         if (num_count[i] > 0)tmp.push_back(make_pair(i, num_count[i]));     }     sort(tmp.begin(), tmp.end(),compare);  //문제 조건대로 정렬     v.clear();     for (int i = 0; i < tmp.size(); i++)     {         if (v.size() > 100)break;   //행 또는 열이 100넘어가는건 다 버림         v.push_back(tmp[i].first);         v.push_back(tmp[i].second);     } }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       int r, c, k;     cin >> r >> c >> k;       for (int i = 0; i < 3; i++)     {         for (int j = 0; j < 3; j++)         {             cin >> buffer[i][j];         }     }           int row=3;     int column=3;       int time = 0;     while (1)     {         if (buffer[r-1][c-1] == k)break;  //조건 충족 탈출         if (time > 100)   //100초 넘어가면 -1출력         {             time = -1;             break;         }           if (row >= column)         {             int maxx = 0;             for (int i = 0; i < row; i++)             {                 vector<int> v;                 for (int j = 0; j < column; j++)                 {                     v.push_back(buffer[i][j]);                 }                 sorting(v);//row 문제 조건대로 정렬                   int j = 0;                 maxx = max(maxx, (int)v.size());  //row중에 젤 긴게 row size가 됨                 for (; j < v.size(); j++)                 {                     buffer[i][j] = v[j];                                       }                 for (; j < column; j++)                 {                     buffer[i][j] = 0;                 }             }             column = maxx;         }         else         {             int maxx = 0;             for (int j = 0; j < column; j++)             {                 vector<int> v;                 for (int i = 0; i < row; i++)                 {                     v.push_back(buffer[i][j]);                 }                 sorting(v);//row 문제 조건대로 정렬                   int i = 0;                 maxx = max(maxx, (int)v.size());  //row중에 젤 긴게 row size가 됨                 for (; i < v.size(); i++)                 {                     buffer[i][j] = v[i];                   }                 for (; i < row; i++)                 {                     buffer[i][j] = 0;                 }             }             row = maxx;         }           time++;     }     cout << time;       return 0; }

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.