풀기 전:
처음에는 문제가 무슨 말인지 이해하지 못하였다. 그런데 이전 문제인 2630 번과 비교해서 풀었더니 더욱 잘 이해가 되었다.
이 백준 2630 번의 풀이 방법을 거의 가져와서 풀었다.
다만 달라진 점은 1과 0이 붙어있어서 처음부터 2차원 배열에 입력받기는 쉽지 않았다.
그러므로 먼저 문자열을 입력받은후 그것을 바탕으로 배열을 채워넣었어야 했다.
자바(JAVA)
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Collections;
public class Main{
static int arr[][];
public static boolean isAllSame(int startPosX,int startPosY,int n){
int firstNum=arr[startPosX][startPosY];
boolean Same=true;
for(int i=startPosX;i<startPosX+n;i++){
for(int j=startPosY;j<startPosY+n;j++){
if(firstNum!=arr[i][j]){
Same=false;
break;
}
}
}
return Same;
}
public static void DivideBlue(int startPosX,int startPosY,int n){
if(n==1){
System.out.print(arr[startPosX][startPosY]);
return;
}
else if(isAllSame(startPosX,startPosY,n)){
System.out.print(arr[startPosX][startPosY]);
return;
}
else{
System.out.print("(");
DivideBlue(startPosX,startPosY,n/2);
DivideBlue(startPosX,startPosY+n/2,n/2);
DivideBlue(startPosX+n/2,startPosY,n/2);
DivideBlue(startPosX+n/2,startPosY+n/2,n/2);
System.out.print(")");
}
}
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
arr=new int[n][n];
String stringArr[]=new String[n];
for(int i=0;i<n;i++){
stringArr[i]= scanner.next();
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
arr[i][j]=stringArr[i].charAt(j)-'0';
}
}
DivideBlue(0,0,n);
}
}C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int** arr;
bool isAllSame(int startPosX, int startPosY, int n) {
int firstNum = arr[startPosX][startPosY];
bool Same = true;
for (int i = startPosX; i < startPosX + n; i++) {
for (int j = startPosY; j < startPosY + n; j++) {
if (firstNum != arr[i][j]) {
Same = false;
break;
}
}
}
return Same;
}
void DivideBlue(int startPosX, int startPosY, int n) {
if (n == 1) {
cout << arr[startPosX][startPosY];
}
else if (isAllSame(startPosX, startPosY, n)) {
cout << arr[startPosX][startPosY];
}
else {
cout << "(";
DivideBlue(startPosX, startPosY, n / 2);
DivideBlue(startPosX, startPosY+n/2, n / 2);
DivideBlue(startPosX + n / 2, startPosY, n / 2);
DivideBlue(startPosX + n / 2, startPosY + n / 2, n / 2);
cout << ")";
}
}
int main(void) {
int n;
cin >> n;
arr = new int* [n];
for (int i = 0; i < n; i++) {
arr[i] = new int[n];
}
string* stringArr = new string[n];
for (int i = 0; i < n; i++) {
cin >> stringArr[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = stringArr[i][j] - '0';
}
}
DivideBlue(0, 0, n);
}6개월 후에 다시 풀었을때:
import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.*;
public class Main {
static int arr[][];
public static void divide(int n,int first,int second){
boolean needDivide=false;
int firstThing=arr[first][second];
for(int i=first;i<first+n;i++){
for(int j=second;j<second+n;j++){
if(firstThing!=arr[i][j]){
needDivide=true;
}
}
}
if(!needDivide){
System.out.print(Integer.toString(firstThing));
}
else {
System.out.print("(");
int tmp = arr[first][second];
boolean firstNeedMore = false;
for (int i = first; i < first + (n / 2); i++) {
for (int j = second; j < second + (n / 2); j++) {
if (tmp != arr[i][j]) {
firstNeedMore = true;
}
}
}
if (firstNeedMore) {
// System.out.print("(");
divide(n / 2, first, second);
// System.out.print(")");
} else {
System.out.print(Integer.toString(tmp));
}
tmp = arr[first][second + (n / 2)];
boolean secondNeedMore = false;
for (int i = first; i < first + (n / 2); i++) {
for (int j = second + (n / 2); j < second+n; j++) {
if (tmp != arr[i][j]) {
secondNeedMore = true;
}
}
}
if (secondNeedMore) {
// System.out.print("(");
divide(n / 2, first, second + (n / 2));
//System.out.print(")");
} else {
System.out.print(Integer.toString(tmp));
}
tmp = arr[first + (n / 2)][second];
boolean thirdNeedMore = false;
for (int i = first + (n / 2); i < first+n; i++) {
for (int j = second; j < second + (n / 2); j++) {
if (tmp != arr[i][j]) {
thirdNeedMore = true;
}
}
}
if (thirdNeedMore) {
//System.out.print("(");
divide(n / 2, first + (n / 2), second);
//System.out.print(")");
} else {
System.out.print(Integer.toString(tmp));
}
tmp = arr[first + (n / 2)][second + (n / 2)];
boolean fourthNeedMore = false;
for (int i = first + (n / 2); i <first+ n; i++) {
for (int j = second + (n / 2); j <second+ n; j++) {
if (tmp != arr[i][j]) {
fourthNeedMore = true;
}
}
}
if (fourthNeedMore) {
// System.out.print("(");
divide(n / 2, first + (n / 2), second + (n / 2));
// System.out.print(")");
} else {
System.out.print(Integer.toString(tmp));
}
System.out.print(")");
}
}
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n=scanner.nextInt();
arr=new int[n+1][n+1];
for(int i=1;i<=n;i++){
String k=scanner.next();
for(int j=1;j<=n;j++){
arr[i][j]=k.charAt(j-1)-'0';
}
}
divide(n,1,1);
}
}이전 문제를 푼 비효율적인 방식을 끝까지 응용했다. 역시 코드가 길어지니 헷갈리는 부분과 틀리는 부분이 증가되었었다.
기록을 통해 실력을 쌓아가자