백준 1051번 문제 : 숫자 정사각형(JAVA)

 

문제설명

---

 

4 꼭지점이 같은 정사각형을 찾는 문제이다.

 

풀이 방법

---

일단 입력 받은 열과 행 중 가장 작은것을 기준으로 반복을 시킨다. 이유는 3행 5열일때 정사각형은 3이상의 크기로 나올 수 없기 때문이다. 그러면서 최대값이 나올 때마다 정답을 갱신시켜준다.

 

코드

---

package pro;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test1 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int[][] arr = new int[a][b];

		for (int i = 0; i < a; i++) {
			String t = br.readLine();
			for (int j = 0; j < b; j++) {
				arr[i][j] = t.charAt(j) - '0';
			}
		}
		int answer = 0;
		//1. 3과 5 중에 더 큰 숫자를 찾고 거기서부터 -1 로 내려와야함
		int small = a<=b?a:b; //a가 b 이상이면 a 가 big에 들어감. 반대의경우는 b가 big에 들어감
		for(int i = 1; i < small; i++) { // 기준점에서 각꼭지점 4번만 반복돌리면 됨.
			for(int j = 0; j< a-i; j++) {
				for(int k =0; k< b-i; k++) {
					if(arr[j][k]==arr[j+i][k]&&arr[j][k]==arr[j][k+i]&&arr[j][k]==arr[j+i][k+i]) {
						answer = i+1;
					}
				}
			}
		}
		if(answer==0) {
			answer=1;
		}
		System.out.println(answer*answer);

	}

}

 

다른 풀이방법

---

loop:for 을 통해 전체 포문을 묶어버리고 가장 큰 정삼각형부터 역으로 찾아가면서 가장 큰 정사각형이 나옴과 동시에 3중 포문을 종료시키면 바로 정답이 나오게된다.

그렇게 되면 효율성이 늘어난다.