728x90
반응형
https://www.acmicpc.net/problem/17140
17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ17140
//
// Created by 최화연 on 2022/04/14.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int row, col, k;
int A[101][101] = {0, };
int R = 3;
int C = 3;
struct Item {
int num;
int cnt;
};
struct cmp {
bool operator() (Item a, Item b) {
if (a.cnt == b.cnt) {
return a.num > b.num;
}
return a.cnt > b.cnt;
}
};
int sort_A() {
int sec = 0;
while (sec < 100) {
if (A[row][col] == k) return sec;
sec ++;
//C 연산
if (R < C) {
int new_R = 0;
for (int c=1; c<=C; c++) {
int visit[101] = {0, };
for (int r=1; r<=R; r++) {
visit[A[r][c]]++;
}
priority_queue<Item, vector<Item>, cmp> pq;
for (int i=1; i<101; i++) {
if (visit[i] > 0) {
pq.push({i, visit[i]});
}
}
int r = 1;
while (!pq.empty()) {
Item item = pq.top();
pq.pop();
if (r > 100) break;
A[r][c] = item.num;
if (r > new_R) new_R = r;
r++;
if (r > 100) break;
A[r][c] = item.cnt;
if (r > new_R) new_R = r;
r++;
}
//나머지 0으로 채우기
for (int rr=r; rr<=100; rr++) {
A[rr][c] = 0;
}
}
R = new_R;
}
//R 연산
else {
int new_C = 0;
for (int r=1; r<=R; r++) {
int visit[101] = {0, };
for (int c=1; c<=C; c++) {
visit[A[r][c]]++;
}
priority_queue<Item, vector<Item>, cmp> pq;
for (int i=1; i<101; i++) {
if (visit[i] > 0) {
pq.push({i, visit[i]});
}
}
int c = 1;
while (!pq.empty()) {
Item item = pq.top();
pq.pop();
if (c > 100) break;
A[r][c] = item.num;
if (c > new_C) new_C = c;
c++;
if (c > 100) break;
A[r][c] = item.cnt;
if (c > new_C) new_C = c;
c++;
}
//나머지 0으로 채우기
for (int cc=c; cc<=100; cc++) {
A[r][cc] = 0;
}
}
C = new_C;
}
}
if (A[row][col] == k) return sec;
return -1;
}
int main(int argc, const char * argv[]) {
cin >> row >> col >> k;
for(int i=1; i<=3; i++) {
for(int j=1; j<=3; j++) {
cin >> A[i][j];
}
}
cout << sort_A() << endl;
return 0;
}풀이 과정
풀이 시간 1시간 6분
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int row, col, k;
int A[101][101] = {0, };
int R = 3;
int C = 3;
struct Item {
int num;
int cnt;
};
struct cmp {
bool operator() (Item a, Item b) {
if (a.cnt == b.cnt) {
return a.num > b.num;
}
return a.cnt > b.cnt;
}
};
int sort_A() {
int sec = 0;
while (sec < 100) {
if (A[row][col] == k) return sec;
sec ++;
//C 연산
if (R < C) {
int new_R = 0;
for (int c=1; c<=C; c++) {
int visit[101] = {0, };
for (int r=1; r<=R; r++) {
visit[A[r][c]]++;
}
priority_queue<Item, vector<Item>, cmp> pq;
for (int i=1; i<101; i++) {
if (visit[i] > 0) {
pq.push({i, visit[i]});
}
}
int r = 1;
while (!pq.empty()) {
Item item = pq.top();
pq.pop();
if (r > 100) break;
A[r][c] = item.num;
if (r > new_R) new_R = r;
r++;
if (r > 100) break;
A[r][c] = item.cnt;
if (r > new_R) new_R = r;
r++;
}
//나머지 0으로 채우기
for (int rr=r; rr<=100; rr++) {
A[rr][c] = 0;
}
}
R = new_R;
}
//R 연산
else {
int new_C = 0;
for (int r=1; r<=R; r++) {
int visit[101] = {0, };
for (int c=1; c<=C; c++) {
visit[A[r][c]]++;
}
priority_queue<Item, vector<Item>, cmp> pq;
for (int i=1; i<101; i++) {
if (visit[i] > 0) {
pq.push({i, visit[i]});
}
}
int c = 1;
while (!pq.empty()) {
Item item = pq.top();
pq.pop();
if (c > 100) break;
A[r][c] = item.num;
if (c > new_C) new_C = c;
c++;
if (c > 100) break;
A[r][c] = item.cnt;
if (c > new_C) new_C = c;
c++;
}
//나머지 0으로 채우기
for (int cc=c; cc<=100; cc++) {
A[r][cc] = 0;
}
}
C = new_C;
}
}
if (A[row][col] == k) return sec;
return -1;
}
int main(int argc, const char * argv[]) {
cin >> row >> col >> k;
for(int i=1; i<=3; i++) {
for(int j=1; j<=3; j++) {
cin >> A[i][j];
}
}
cout << sort_A() << endl;
return 0;
}이전 풀이
풀이 시간 2시간 35분
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int A[100][100] = {0,};
int new_A[100][100] = {0,};
int R, C, K;
int sec = 0;
struct items{
int num;
int cnt;
};
struct cmp{
bool operator()(items x, items y){
//등장 횟수가 같은 경우
if(x.cnt == y.cnt){
//2. 수가 커지는 순으로
return x.num > y.num;
}
//1. 등장 횟수가 커지는 순으로
return x.cnt > y.cnt;
}
};
int main(int argc, const char * argv[]) {
cin >> R >> C >> K;
R--;
C--;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cin >> A[i][j];
}
}
int r_cnt = 3;
int c_cnt = 3;
while(sec <= 100){
//행 개수 구하기 - 각 열에 대하여 행을 0~99까지 탐색하면서 0이 나오기 이전 개수를 센다, 최댓값이 행의 개수
r_cnt = 0;
for(int c=0; c<100; c++){
int cnt = 0;
for(int r=0; r<100; r++){
if(A[r][c] == 0) break;
cnt++;
}
if(cnt > r_cnt) r_cnt = cnt;
}
//열 개수 구하기 - 각 행에 대하여 열을 0~99까지 탐색하면서 0이 나오기 이전 개수를 센다, 최댓값이 열의 개수
c_cnt = 0;
for(int r=0; r<100; r++){
int cnt = 0;
for(int c=0; c<100; c++){
if(A[r][c] == 0) break;
cnt++;
}
if(cnt>c_cnt) c_cnt = cnt;
}
//정답 체크 - 현재 배열의 행, 열이 R, C를 포함하는 경우, A[R][C] == K이면 현재 시간을 출력하고 종료한다
if(r_cnt >= R && c_cnt >= C){
if(A[R][C] == K){
cout << sec << endl;
return 0;
}
}
//R연산
if(r_cnt >= c_cnt){
//각 행에 대하여
for(int r=0; r<r_cnt; r++){
//1. 등장 횟수 세기 - 열을 탐색하여 숫자의 등장 횟수를 visit 배열을 통해 카운팅
int visit[101] ={0,};
for(int c=0; c<c_cnt; c++){
visit[A[r][c]]++;
}
//2. 정렬 - 등장 횟수가 한 번 이상인 숫자들을 priority_queue에 Push
priority_queue<items, vector<items>, cmp> pq;
for(int n=1; n<=100; n++){
if(visit[n] > 0){
pq.push({n, visit[n]});
}
}
//3. new_A에 추가 - pq 안의 item(숫자, 등장 횟수)를 각 열에 차례대로 넣는다
int item_cnt = pq.size();
for(int c=0; c<item_cnt*2; c+=2){
//열의 범위를 초과하는 경우, 이후 item들은 넣지 않는다
if(c==100) break;
new_A[r][c] = pq.top().num;
new_A[r][c+1] = pq.top().cnt;
pq.pop();
}
}
}
//C연산
else{
//각 열에 대하여
for(int c=0; c<c_cnt; c++){
//1. 등장 횟수 세기 - 행을 탐색하여 숫자의 등장 횟수를 visit 배열을 통해 카운팅
int visit[101] ={0,};
for(int r=0; r<r_cnt; r++){
visit[A[r][c]]++;
}
//2. 정렬 - 등장 횟수가 한 번 이상인 숫자들을 priority_queue에 Push
priority_queue<items, vector<items>, cmp> pq;
for(int i=1; i<=100; i++){
if(visit[i] > 0){
pq.push({i, visit[i]});
}
}
//3. new_A에 추가 - pq 안의 item(숫자, 등장 횟수)를 각 행에 차례대로 넣는다
int item_cnt = pq.size();
for(int r=0; r<item_cnt*2; r+=2){
//행의 범위를 초과하는 경우, 이후 item들은 넣지 않는다
if(r==100) break;
new_A[r][c] = pq.top().num;
new_A[r+1][c] = pq.top().cnt;
pq.pop();
}
}
}
//A = new_A, new_A 초기화
for(int i=0; i<100; i++){
for(int j=0; j<100; j++){
A[i][j] = new_A[i][j];
new_A[i][j] = 0;
}
}
sec++;
}
cout << -1 << endl;
return 0;
}
//시간복잡도 = T(sec*(2*100*100 + r_cnt*(c_cnt + n log2 n + n log2 n) + 100*100)) -> O(n^3 log n)
//sec = 100, r_cnt = c_cnt = 100, n = 100인 경우, 약 17,287,712번 연산
//0.5초 -> 50,000,000번 연산
//공간복잡도 = S(2*100*100 + sec*(101+2*n)) -> O(n^3)728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 11659 구간 합 구하기 4 Python3 (0) | 2021.08.18 |
|---|---|
| 백준 11725 트리의 부모 찾기 Python3 (0) | 2021.08.18 |
| 백준 11501 주식 Python3 (0) | 2021.08.16 |
| 백준 16235 나무 재테크 C++ (2) | 2021.08.15 |
| 백준 8980 택배 Python3 (0) | 2021.08.12 |