백준(boj) 17140_이차원 배열과 연산 (파이썬, c++)

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

풀이

---

#3*3배열 A #R: 모든 행에 대해서 행의 개수 >= 열의개수 일때 적용 #C: 모든 열에 대해서 행의개수 <열의 개수 일때 적용 #정렬, 수와 등장횟수 #수의 등장횟수가 커지는 순으로, 이게 여러개면 수가 커지는 순으로(모두 오름차순) #R:: 행의 크기 가장 큰 행을 기준으로 행 확장, 100개 넘어가면 나머지 버림 #C:: 열의 크기 가장 큰 열을 기준으로 열 확장(0으로) 단, 정렬시 0무시

=> cnt에 입력하면서 a[][]를 0으로 바꿔줌으로써 해결, 정렬시 0무시는 a[][]가 0이 아닌지 확인하여 해결

#A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간 #저 규칙대로 구해서 A[r][c]==k면 종료, 시간출력, 100넘어가면 -1출력

python3

from sys import*
from collections import*
input = stdin.readline
def solve():
    global n,m
    for t in range(101):
        if a[r-1][c-1] == k: return t
        if n >= m:
            for i in range(n):
                cnt = [0]*101
                for j in range(m):
                    if a[i][j]:
                        cnt[a[i][j]]+=1
                        a[i][j]=0
                b=[]
                for j in range(101):
                    if cnt[j]:b.append((cnt[j], j))
                b.sort()
                m = max(m, len(b)*2)
                j=0
                for x in b:
                    a[i][j+1], a[i][j] = x
                    j+=2
        else:
            for i in range(m):
                cnt = [0]*101
                for j in range(n):
                    if a[j][i]:
                        cnt[a[j][i]]+=1
                        a[j][i]=0
                b=[]
                for j in range(101):
                    if cnt[j]:b.append((cnt[j], j))
                b.sort()
                n = max(n, len(b)*2)
                j=0
                for x in b:
                    a[j+1][i], a[j][i] = x
                    j+=2
    return -1
r,c,k = map(int,input().split())
a=[[0]* 101 for _ in range(101)]
for i in range(3):
    a[i][0], a[i][1], a[i][2] = map(int,input().split())
n, m = 3, 3
print(solve())

C++

#include<cstdio>        //입출력 
#include<vector>        //vector 
#include<algorithm>        //sort(), max()
using namespace std;
const int SIZE = 101;
int r, c, k, n=3, m=3;
int a[SIZE][SIZE];
typedef pair<int, int> P;
int solve(){
    for(int t=0; t<101; t++){
        if(a[r-1][c-1]==k) return t; 
        if(n>=m){        //R연산 
            for(int i=0; i<n; i++){
                int cnt[SIZE]={0,};                            //초기화 잘 시켜주기 
                for(int j=0; j<m; j++){
                    if(a[i][j]){
                    cnt[a[i][j]]++;
                    a[i][j]=0;
                    }
                }
                vector<P> v;
                for(int j=0; j<101; j++){
                    if(cnt[j]) v.push_back({cnt[j], j});    //개수,  수 
                }
                sort(v.begin(), v.end());
                int v_size = v.size();                        //max에 type pair인 v.size()랑 비교했다가 에러남 
                m = max(m, v_size*2);                        //두 개의 원소로 정렬, 길이는 두배 
                int j=0;
                for(auto x: v){
                    a[i][j+1] = x.first;                    //배열에는 수 먼저 넣음 
                    a[i][j] = x.second;
                    j+=2;
                }
            }
        }
        else{            //C연산
            for(int i=0; i<m; i++){
                int cnt[SIZE]={0,};
                for(int j=0; j<n; j++){
                    if(a[j][i]){
                        cnt[a[j][i]]++;
                        a[j][i]=0;
                    }
                }
                vector<P> v;
                for(int j=0; j<101; j++){
                    if(cnt[j]) v.push_back({cnt[j], j});
                }
                sort(v.begin(), v.end());
                int v_size = v.size();
                n = max(n, v_size*2);
                int j=0;
                for(auto x: v){
                    a[j+1][i] = x.first;
                    a[j][i] = x.second;
                    j+=2;
                }
            } 
        }
    }
    return -1;
}
int main(){
    scanf("%d %d %d", &r, &c, &k);
    for(int i=0; i<3; i++)
        scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
    printf("%d", solve());
    return 0;
}

고찰

---

c++:: 초기화 잘 시켜주기, type <int, int>인 v로 max(n, v.size()*2) 했다가 에러남, 그 전에 변수로 설정해서 type 맞춰주기

공부시 참고한 곳: https://rebas.kr/844