[백준][삼성 SW 역량 테스트][Gold 4][C++] 17140 이차원 배열과 연산

문제

백준 삼성 SW 역량 테스트 기출 문제 - 17140 이차원 배열과 연산 (Gold 4)

17140번: 이차원 배열과 연산

 

---

문제 풀이

접근 방식

주어진 A 배열에 1초마다 아래의 연산을 수행할 때, A[r][c]의 값이 k가 되기 위한 최소 시간을 구하는 문제이다.

 

R 연산과 C 연산

 

먼저, A를 100 × 100 크기의 배열로 만들고, 모든 값을 0으로 초기화해주었다.

A에 입력값을 저장하고 행의 개수 row와 열의 개수 col을 3으로 설정해준 후,

while문에서 연산을 수행하였다.

 

우선, R 연산을 수행하기 위해 map을 사용하여 한 행에 있는 숫자들의 개수를 세어주었다.

그 후, 숫자의 개수 기준 오름차순, 숫자 기준 오름차순으로 정렬되도록 설정한 우선순위 큐에

map에 저장한 숫자(key)와 개수(value)를 넣어주었다.

큐에 저장된 값을 활용하여 R 연산의 결과를 A 배열에 저장해주었고, 최대 행의 크기를 col에 저장해주었다.

(이때, 행과 열의 크기가 100을 넘어가면 안 되기 때문에 이를 고려하여 구현하여야 한다.)

C 연산은 R 연산과 로직은 같고, 방향만 행에서 열로 바꿔 구현해주었다.

 

while문은 A[r-1][c-1]의 값이 k 일 때까지 수행되도록 구현하였고,

시간이 100초가 넘어가면 -1을 출력해주도록 하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second == b.second)
			return a.first > b.first;
		else
			return a.second > b.second;
	}
};

int main() {
	int r, c, k;
	cin >> r >> c >> k;
	int A[100][100] = { 0 };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> A[i][j];
		}
	}

	int answer = 0;
	int row = 3, col = 3, cnt = 0;
	int i, j;
	unordered_map<int, int> dic;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	while (A[r - 1][c - 1] != k) {
		if (answer == 100) {
			answer = -1;
			break;
		}

		if (row >= col) {	// R 연산
			for (i = 0; i < row; i++) {
				cnt = 0;
				dic.clear();
				for (j = 0; j < col; j++) {
					if (A[i][j] == 0) continue;
					dic[A[i][j]]++;
				}
				for (auto d : dic) {
					pq.push({ d.first, d.second });
					cnt++;
				}

				for (j = 0; j < cnt; j++) {
					if (j == 50){
						while (!pq.empty()) pq.pop();
						break;
					}
					A[i][j * 2] = pq.top().first;
					A[i][j * 2 + 1] = pq.top().second;
					pq.pop();
				}
				for (int k = j * 2; k < row; k++)
					A[i][k] = 0;

				if (cnt * 2 > col && cnt <= 50)
					col = cnt * 2;
			}
		}
		else {	// C 연산
			for (i = 0; i < col; i++) {
				cnt = 0;
				dic.clear();
				for (int j = 0; j < row; j++) {
					if (A[j][i] == 0) continue;
					dic[A[j][i]]++;
				}
				for (auto d : dic) {
					pq.push({ d.first, d.second });
					cnt++;
				}

				for (j = 0; j < cnt; j++) {
					if (j == 50) {
						while (!pq.empty())	pq.pop();
						break;
					}
					A[j * 2][i] = pq.top().first;
					A[j * 2 + 1][i] = pq.top().second;
					pq.pop();
				}
				for (int k = j * 2; k < row; k++)
					A[k][i] = 0;

				if (cnt * 2 > row && cnt <= 50)
					row = cnt * 2;
			}
		}

		answer++;
	}

	cout << answer;
}

실행 결과

실행 결과 : 통과 (4ms)