ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ] 17140번 이차원 배열과 연산
    알고리즘/BOJ 2020. 7. 31. 19:14

    https://www.acmicpc.net/problem/17140

     

    17140번: 이차원 배열과 연산

    첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

    www.acmicpc.net

    아이디어

    1, 행 정렬과 열 정렬을 함수를 구분하여 동작하게 해 준다.

     

    2, 행 혹은 열을 정렬할 때 각각의 숫자와 등장 횟수를 담는 구조체를 선언을 한 다음 벡터에 저장을 해 준다.

     

    3, compare함수를 통하여 문제의 조건인 "등장 횟수가 커지는 식으로, 그 수가 같다면 수가 커지는 순으로" 벡터에 있는 구조체를 정렬한다.

     

    4, 행 혹은 열을 위와 같은 방식으로 연산을 진행하고 문제의 조건에 맞게 답을 출력한다. 

     

    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int arr[101][101];
    
    typedef struct info {
    	int num;
    	int cnt;
    }info;
    
    int row_cnt, col_cnt;
    int num_cnt[101];
    int r, c, k;
    
    bool compare(info a, info b) {
    	if (a.cnt < b.cnt) {
    		return true;
    	}
    	else if (a.cnt > b.cnt) {
    		return false;
    	}
    	else {
    		if (a.num < b.num) {
    			return true;
    		}
    		else {
    			return false;
    		}
    	}
    }
    
    vector<info> num_count() {
    	info insert;
    	vector<info> res;
    	for (int j = 1; j < 101; j++) {
    		if (num_cnt[j] != 0) {
    			insert.num = j;
    			insert.cnt = num_cnt[j];
    			res.push_back(insert);
    		}
    	}
    
    	return res;
    }
    
    void row_calc() {
    	//행에 대하여 정렬
    	vector<info> renewal;
    	vector<info>::iterator iter;
    	vector<int> renewal2;
    	int max_len = 0;
    
    	for (int i = 0; i < row_cnt; i++) {
    		memset(num_cnt, 0, sizeof(num_cnt));
    		renewal.clear();
    		renewal2.clear();
    		for (int j = 0; j < col_cnt; j++) {
    			num_cnt[arr[i][j]]++;
    		}
    
    		renewal = num_count();
    
    		sort(renewal.begin(), renewal.end(), compare);
    
    		for (iter = renewal.begin(); iter != renewal.end(); iter++) {
    			renewal2.push_back(iter->num);
    			renewal2.push_back(iter->cnt);
    		}
    
    		for (int j = 0; j < col_cnt; j++) {
    			arr[i][j] = 0;
    		}
    
    
    		int renewal2_size = renewal2.size();
    		for (int j = 0; j < renewal2_size; j++) {
    			if (j == 100) break;
    			arr[i][j] = renewal2[j];
    		}
    
    		if (max_len < renewal2.size()) max_len = renewal2_size;
    	}
    
    	if (max_len > 100) max_len = 100;
    	col_cnt = max_len;
    
    
    }
    
    void col_calc() {
    	//열에 대하여 정렬
    	vector<info> renewal;
    	vector<info>::iterator iter;
    	vector<int> renewal2;
    	info insert;
    	int max_len = 0;
    
    	for (int i = 0; i < col_cnt; i++) {
    		memset(num_cnt, 0, sizeof(num_cnt));
    		renewal.clear();
    		renewal2.clear();
    		for (int j = 0; j < row_cnt; j++) {
    			num_cnt[arr[j][i]]++;
    		}
    
    
    		renewal = num_count();
    
    		sort(renewal.begin(), renewal.end(), compare);
    
    		for (iter = renewal.begin(); iter != renewal.end(); iter++) {
    			renewal2.push_back(iter->num);
    			renewal2.push_back(iter->cnt);
    		}
    
    		for (int j = 0; j < row_cnt; j++) {
    			arr[j][i] = 0;
    		}
    
    
    		int renewal2_size = renewal2.size();
    		for (int j = 0; j < renewal2_size; j++) {
    			if (j == 100) break;
    			arr[j][i] = renewal2[j];
    		}
    
    		if (max_len < renewal2.size()) max_len = renewal2_size;
    	}
    
    	if (max_len > 100) max_len = 100;
    	row_cnt = max_len;
    }
    
    
    int main()
    {
    	int temp;
    	vector<int> insert;
    	int res = 0;
    	scanf("%d %d %d", &r, &c, &k);
    
    	for (int i = 0; i < 3; i++) {
    		insert.clear();
    		for (int j = 0; j < 3; j++) {
    			scanf("%d", &temp);
    			arr[i][j] = temp;
    		}
    
    	}
    
    	row_cnt = 3;
    	col_cnt = 3;
    
    	while (1) {
    		if (res > 100) break;
    
    		if (arr[r - 1][c - 1] == k) {
    			break;
    		}
    
    		if (row_cnt >= col_cnt) row_calc();
    		else col_calc();
    
    		res++;
    
    	}
    
    	if (res == 101) {
    		printf("%d\n", -1);
    	}
    	else {
    		printf("%d\n", res);
    	}
    
    
    	return 0;
    }

    '알고리즘 > BOJ' 카테고리의 다른 글

    [BOJ]16234번 인구 이동  (0) 2020.08.14
    [BOJ] 17837번 새로운 게임2  (0) 2020.08.04
    [BOJ] 15684번 사다리 조작  (0) 2020.07.31
    [BOJ] 15683번 감시  (0) 2020.07.30
    [BOJ] 14891번 톱니바퀴  (0) 2020.07.30
Designed by Tistory.