백준(BOJ) 17140번 이차원 배열과 연산

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

문제

크기가 3×3인 배열 A가 있다. 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가 되기 위한 최소 시간을 구해보자.

풀이 :

행 >= 열 이라면 행을 아니라면 열을 탐색하자.

 탐색시 vector<pair<int,int>> 를 통하여 나온숫자 횟수, 숫자 로 담은후 오름차순 정렬해서 second , first 순으로 할당해주자.

행 or 열에 탐색이 한번끝났다면 가장 큰 행 or 열의 수를 기억해놨다가 행이라면 열을 열이라면 행을 그 수로 바꿔주자.

코드 ( C ++ )

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int r, c, k;

int A[100][100];

int main()

{

cin >> r >> c >> k;

for (int i = 0; i < 3; ++i)

for (int j = 0; j < 3; ++j)

cin >> A[i][j];

int row = 3, col = 3;

int time = 0;

// 바로 조건 만족시 종료

if (A[r - 1][c - 1] == k)

{

cout << 0 << "\n";

return 0;

}

while (1) {

if (time > 100) {

cout << -1 << "\n";

break;

}

time++;

if (row >= col)

{

//갱신을 위한 숫자

int changenum = 0;

// 한 행씩 시작한다.

for (int i = 0; i < row; ++i)

{

vector<pair<int, int>> v;

// 횟수를 위한 배열

int numbers[100+1] = { 0, };

for (int j = 0; j < col; ++j)

{

numbers[A[i][j]]++;

}

for (int j = 1; j <= 100; ++j)

{

// v배열에 나온횟수, 숫자 쌍을 기록한다.

if (numbers[j])

v.push_back(make_pair(numbers[j], j));

}

// 오름차순으로 정렬한다.

sort(v.begin(), v.end());

// A 초기화

for (int j = 0; j < 100; ++j)

A[i][j] = 0;

int temp = 0;

for (int j = 0; j < v.size(); ++j)

{

A[i][temp] = v[j].second;

temp++;

A[i][temp] = v[j].first;

temp++;

}

changenum = max(changenum, temp);

}

// 열 갱신

col = changenum;

}

else

{

int changenum = 0;

// 한 열씩 시작한다.

for (int i = 0; i < col; ++i)

{

vector<pair<int, int>> v;

// 횟수를 위한 배열

int numbers[100+1] = { 0, };

for (int j = 0; j < row; ++j)

{

numbers[A[j][i]]++;

}

for (int j = 1; j <= 100; ++j)

{

// v배열에 나온횟수, 숫자 쌍을 기록한다.

if (numbers[j])

v.push_back(make_pair(numbers[j], j));

}

// 오름차순으로 정렬한다.

sort(v.begin(), v.end());

// A 초기화

for (int j = 0; j < 100; ++j)

A[j][i] = 0;

int temp = 0;

for (int j = 0; j < v.size(); ++j)

{

A[temp][i] = v[j].second;

temp++;

A[temp][i] = v[j].first;

temp++;

}

changenum = max(changenum, temp);

}

// 행 갱신

row = changenum;

}

if (A[r - 1][c - 1] == k)

{

cout << time << "\n";

break;

}

}

return 0;

}