백준 1051번- 숫자 정사각형

처음 풀이 

#include <bits/stdc++.h>
using namespace std;

int n, m, s, c=0;
vector<vector<char>> v;       
vector<int> area;

int main(){
	cin >> n >> m;
	v = vector<vector<char>>(n, vector<char>(m));
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> v[i][j];
		}
	}
	while(c < min(n, m)){
		for(int i=0; i < n-c; i++){
			for(int j =0; j < m-c; j++){
				int st = v[i][j];
				if(st == v[i][j+c] && st == v[i+c][j] && st == v[i+c][j+c]){
					s=(c+1)*(c+1);
					area.push_back(s);
				}
			}
		}
		c+=1;		
	}
	
	cout << area.back();
	
	return 0;
}

area 동적 배열을 만들어서 정사각형이 생길 때마다 push_back하여 정사각형 넓이를 집어 넣었다.

제일 마지막 배열의 원소가 가장 큰 정사각형의 넓이 값이므로 area.back()을 하여 area 배열의 가장 마지막 원소를 출력해줬다. 

 

새로운 배열은 만들어서 거기에 정사각형의 넓이를 넣는 과정이 굳이 필요할까라는 생각이 들었다. 

비효율적인 것 같아 max(a,b)를 사용하여 정사각형 넓이의 최대값을 구하는 방법으로 수정했다.

 

수정 풀이

#include <bits/stdc++.h>
using namespace std;

int n, m, s, c=0, maxValue=0;
vector<vector<char>> v;       
vector<int> area;

int main(){
	cin >> n >> m;
	v = vector<vector<char>>(n, vector<char>(m));
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> v[i][j];
		}
	}
	while(c < min(n, m)){
		for(int i=0; i < n-c; i++){
			for(int j =0; j < m-c; j++){
				int st = v[i][j];
				if(st == v[i][j+c] && st == v[i+c][j] && st == v[i+c][j+c]){
					s=(c+1)*(c+1);
					maxValue = max(maxValue, s);
				}
			}
		}
		c+=1;		
	}
	
	cout << maxValue;
	
	return 0;
}

 

첫번째 풀이에서는 사용된 메모리의 크기가 2156KB였지만,

수정된 풀이에서는 사용된 메모리의 크기가 2020KB이다. 

코드를 수정함으로써 사용되는 메모리의 크기가 줄어든 것을 확인할 수 있었다.