BOJ 17140. 이차원 배열과 연산

24-03-13

🙇‍♀️[Gold IV] 이차원 배열과 연산 - 17140

문제 링크

성능 요약

메모리: 2156 KB, 시간: 8 ms

분류

구현, 시뮬레이션, 정렬

제출 일자

2024년 3월 13일 19:02:19

문제 설명

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

🚀풀이

R연산과 C연산을 할 때 정렬을 특수하게 하므로 그에 맞는 구조체를 만들었다.

struct Num
{
	int num, cnt;
	bool operator<(const Num& other)
	{
		if (cnt == other.cnt)
			return num < other.num;
		else
			return cnt < other.cnt;
	}
};

숫자와 숫자가 나온 개수를 담고있다.

로직은 Num을 담는 새로운 벡터를 만들고, 그곳에 숫자와 숫자의 개수를 카운트 해준다.

그 뒤 Num벡터를 정렬하고 정렬된 값에 맞춰서 기존 배열을 갱신한다.

전역변수와 R,C함수는 다음과 같다.
주석으로 각 설명을 더했다.

int r, c, k;
int r_len = 3, c_len = 3;
vector<vector<int>> board;
vector<Num> numbers;

void R()
{
	// 각 수가 얼만큼 나왔는지 알아야한다.
	int max_r_len = 0;
	int max_c_len = 0; // 이게 갱신됨.
	for (int y = 1; y <= r_len; ++y)
	{
		numbers.clear();
		numbers.resize(101);
        // 인덱스가 각 숫자랑 동일하게 만들기.
		for (int i = 1; i <= 100; ++i)
			numbers[i].num = i;

        // 배열의 숫자 카운팅.
		for (int x = 1; x <= c_len; ++x)
		{
			numbers[board[y][x]].cnt++;
		}
        // 카운트가 다 됐으므로 정렬.
		sort(numbers.begin(), numbers.end());

        // 기존 배열 비우기.
		board[y].clear();
        // 1부터 시작하니까 0값을 삽입.
		board[y].push_back(0);
        // 길이 계산용.
		int len = 0;
		for (int i = 1; i <= 100; ++i)
		{
            // 숫자가 0이거나 카운트가 0이라면 스킵.
			if (numbers[i].cnt == 0 || numbers[i].num == 0)
				continue;
            // 숫자부터 삽입.
			board[y].push_back(numbers[i].num);
			len++;
            // 개수 삽입.
			board[y].push_back(numbers[i].cnt);
			len++;
		}
        // 나머지는 0으로 채워주기.
		for (int i = len; i <= 100; ++i)
			board[y].push_back(0);

		max_c_len = max(max_c_len, len);
	}

	c_len = max(c_len, max_c_len);
}

void C()
{
	int max_r_len = 0;
	int max_c_len = 0;
	for (int x = 1; x <= c_len; ++x)
	{
		numbers.clear();
		numbers.resize(101);
		for (int i = 1; i <= 100; ++i)
			numbers[i].num = i;

		for (int y = 1; y <= r_len; ++y)
		{
			numbers[board[y][x]].cnt++;
		}
		sort(numbers.begin(), numbers.end());
		board[0][x] = 0;
		int len = 0;
		int idx = 1;
		for (int i = 1; i <= 100; ++i)
		{
			if (numbers[i].cnt == 0 || numbers[i].num == 0)
				continue;
			board[idx][x] = numbers[i].num;
			idx++;
			len++;
			board[idx][x] = numbers[i].cnt;
			idx++;
			len++;
		}
		max_r_len = max(max_r_len, len);
		for (int i = len + 1; i <= 100; ++i)
		{
			board[i][x] = 0;
		}

	}

	r_len = max(r_len, max_r_len);

}

solve함수는 다음과 같다.

void solve()
{
	// 입력값 받기.
	cin >> r >> c >> k;
	board = vector<vector<int>>(101, vector<int>(101));
	for (int y = 1; y <= 3; ++y)
	{
		for (int x = 1; x <= 3; ++x)
		{
			cin >> board[y][x];
		}
	}

	for (int i = 0; i <= 101; ++i)
	{
        // 100초를 넘겼을 경우.
		if (i == 101)
		{
			cout << -1;
			break;
		}
        // 정답을 찾았을 경우.
		if (board[r][c] == k)
		{
			cout << i;
			break;
		}

		if (r_len >= c_len)
			R();
		else
			C();
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct Num
{
	int num, cnt;
	bool operator<(const Num& other)
	{
		if (cnt == other.cnt)
			return num < other.num;
		else
			return cnt < other.cnt;
	}
};

int r, c, k, total_time = 0;
int r_len = 3, c_len = 3;
vector<vector<int>> board;
vector<Num> numbers;

void R()
{
	// 각 수가 얼만큼 나왔는지 알아야한다.
	int max_r_len = 0;
	int max_c_len = 0; // 이게 갱신됨.
	for (int y = 1; y <= r_len; ++y)
	{
		numbers.clear();
		numbers.resize(101);
		for (int i = 1; i <= 100; ++i)
			numbers[i].num = i;

		for (int x = 1; x <= c_len; ++x)
		{
			numbers[board[y][x]].cnt++;
		}
		sort(numbers.begin(), numbers.end());

		board[y].clear();
		board[y].push_back(0);
		int len = 0;
		for (int i = 1; i <= 100; ++i)
		{
			if (numbers[i].cnt == 0 || numbers[i].num == 0)
				continue;
			board[y].push_back(numbers[i].num);
			len++;
			board[y].push_back(numbers[i].cnt);
			len++;
		}
		for (int i = len; i <= 100; ++i)
			board[y].push_back(0);

		max_c_len = max(max_c_len, len);
	}

	c_len = max(c_len, max_c_len);
}

void C()
{
	int max_r_len = 0;
	int max_c_len = 0;
	for (int x = 1; x <= c_len; ++x)
	{
		numbers.clear();
		numbers.resize(101);
		for (int i = 1; i <= 100; ++i)
			numbers[i].num = i;

		for (int y = 1; y <= r_len; ++y)
		{
			numbers[board[y][x]].cnt++;
		}
		sort(numbers.begin(), numbers.end());
		board[0][x] = 0;
		int len = 0;
		int idx = 1;
		for (int i = 1; i <= 100; ++i)
		{
			if (numbers[i].cnt == 0 || numbers[i].num == 0)
				continue;
			board[idx][x] = numbers[i].num;
			idx++;
			len++;
			board[idx][x] = numbers[i].cnt;
			idx++;
			len++;
		}
		max_r_len = max(max_r_len, len);
		for (int i = len + 1; i <= 100; ++i)
		{
			board[i][x] = 0;
		}

	}

	r_len = max(r_len, max_r_len);

}

void solve()
{
	// 입력값 받기.
	cin >> r >> c >> k;
	board = vector<vector<int>>(101, vector<int>(101));
	for (int y = 1; y <= 3; ++y)
	{
		for (int x = 1; x <= 3; ++x)
		{
			cin >> board[y][x];
		}
	}

	for (int i = 0; i <= 101; ++i)
	{
		if (i == 101)
		{
			cout << -1;
			break;
		}
		if (board[r][c] == k)
		{
			cout << i;
			break;
		}

		if (r_len >= c_len)
			R();
		else
			C();
	}
}

int main() 
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}

Twitter Facebook LinkedIn

BOJ 17140. 이차원 배열과 연산

🙇‍♀️[Gold IV] 이차원 배열과 연산 - 17140

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀전체 코드

공유하기

참고

BOJ 14620. 꽃길

BOJ 13301. 타일 장식물

BOJ 13301. 타일 장식물

BOJ 9934. 완전 이진 트리