관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [백준] 이차원 배열과 연산 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [백준] 이차원 배열과 연산 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:50


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


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

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct rl_len {

	int r_l;
	int c_l;

}rl_len;

int a_r, a_c, a_k;

int map[100][100];

int cnt[101];

rl_len rl;

void swap2(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}


// rotate row and column to use 'sort' fucntion
// use this only if c_len > r_len
void rotate2() {

	for (int i = 0; i < 100; i++) {
		for (int j = i; j < 100; j++) {
			swap2(map[i][j], map[j][i]);
		}
	}

}


void update_rl() {

	int isRow = true;
	int max_r = 0;
	int max_c = 0;
	int temp;

	for (int i = 0; i < 100; i++) {
		temp = 0;
		for (int j = 0; j < 100; j++) {
			
			if (map[i][j] == 0) {
				break;
			}
			temp++;
		}
		max_c = max_c < temp ? temp : max_c;
	}



	for (int j = 0; j < 100; j++) {
		temp = 0;
		for (int i = 0; i < 100; i++) {

			if (map[i][j] == 0) {
				break;
			}
			temp++;
		}
		max_r = max_r < temp ? temp : max_r;
	}

	rl.r_l = max_r;
	rl.c_l = max_c;

}



// sort array in row manner
void sort() {

	int total_len = max(rl.r_l, rl.c_l);

	int row_len = rl.r_l;
	int col_len = rl.c_l;

	// do sort using map
	int max_num = 0;
	int max_dup = col_len;
	vector<int> temp_elem;

	// row_len >= col_len
	if (row_len >= col_len) {

		for (int row = 0; row < row_len; row++) {

			// initialize cnt[101]
			fill(cnt, cnt + 101, 0);

			// fill cnt array
			for (int j = 0; j <= col_len; j++) {

				if (map[row][j] > 0) {
					cnt[map[row][j]]++;
					max_num = max_num < map[row][j] ? map[row][j] : max_num;
				}

			}

			// using cnt array, make temp_elem
			for (int dup = 1; dup <= col_len; dup++) {

				for (int i = 1; i <= max_num; i++) {
					if (cnt[i] == dup) {
						temp_elem.push_back(i);
						temp_elem.push_back(dup);
					}
				}
			}

			// copy temp_elem to map[row][]
			fill_n(&map[row][0], 100, 0);
			for (int i = 0; i < temp_elem.size() && i < 100; i++) {
				map[row][i] = temp_elem[i];
			}
			temp_elem.clear();

		}
	}

	else {

		for (int col = 0; col < col_len; col++) {

			// initialize cnt[101]
			fill(cnt, cnt + 101, 0);

			// fill cnt array
			for (int i = 0; i <= row_len; i++) {

				if (map[i][col] > 0) {
					cnt[map[i][col]]++;
					max_num = max_num < map[i][col] ? map[i][col] : max_num;
				}

			}

			// using cnt array, make temp_elem
			for (int dup = 1; dup <= row_len; dup++) {

				for (int i = 1; i <= max_num; i++) {
					if (cnt[i] == dup) {
						temp_elem.push_back(i);
						temp_elem.push_back(dup);
					}
				}
			}

			// copy temp_elem to map[row][]
			//fill_n(&map[row][0], 100, 0);
			for (int i = 0; i < 100; i++) {
				map[i][col] = 0;
			}

			for (int i = 0; i < temp_elem.size() && i < 100; i++) {
				map[i][col] = temp_elem[i];
			}
			temp_elem.clear();

		}

	}

	update_rl();
}


int main() {

	cin >> a_r >> a_c >> a_k;

	int t = 0;
	rl = { 3, 3 };

	// initialize array
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}
	

	// simulate untill map[a_r][a_c] == a_k
	for (t = 0; t <= 100; t++) {
		
		// check ans
		if (map[a_r-1][a_c-1] == a_k) {
			cout << t << endl;
			return 0;
		}

		// do sort
		sort();

	}

	if (t > 100) {
		cout << -1 << endl;
	}

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

 
0 Comments
댓글쓰기 폼