개발하는지호

[백준/1051/실버3] 숫자 정사각형

by 개발하는지호

코딩테스트

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

 

1051번: 숫자 정사각형

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행

www.acmicpc.net

레벨 실버3

 

<<풀이>>

 

소감 : 문제 자체의 구현은 어렵지가 않았다. 다만 사용한 적이 드문 bufferreader의 안 익숙함이 문제였다.

 

시간복잡도 : O(n^3)

 

주된 개념 : stream(), bufferreader, split

 

풀이 방법 :

각 행의 하나의 값을 지정해두고 그 행을 돌면서 지정해둔 값과 같은지 비교를 한다.

먄약에 같다면 우선, 행에서 같은 값의 길이를 구한다. 그다음 조건 범위 내에서 길이 만큼 떨어진 곳에서의 다른 행에 같은 값이 있는지 찾는다. 이 역시 같다면 그때 그 길이를 제곱해서 넓이를 구하고, Math.max를 통해 최댓값을 도출해낸다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
 
class Main {
    private int solution(int[][] arr, int n, int m){
        int answer= 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = j; k < m; k++) {
                    if(arr[i][j] == arr[i][k] && i + k - j < n && arr[i + k -j][j] == arr[i][j] && arr[i + k -j][k] == arr[i][j]) {
                        answer = Math.max(answer, (k - j + 1)*(k - j + 1));
                    }
                }
             }
        }
        return answer;
    }
 
 
    public static void main(String[] args) throws Exception {
        Main T = new Main();
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] readLine = br.readLine().split(" ");
        int n = Integer.parseInt(readLine[0]);
        int m = Integer.parseInt(readLine[1]);
        String[] tmp = new String[n];
        int[][] arr = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            tmp[i] = br.readLine();
        }
 
        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.asList(tmp[i].split(""))
                    .stream().mapToInt(Integer::parseInt).toArray();
        }
 
 
        System.out.println(T.solution(arr, n, m));
    }
}

 

<<추가 공부>>

 

BufferedReader

 

 

출처 : https://dlee0129.tistory.com/238

 

BufferedReader와 Scanner의 차이

: 이 둘의 속도 차이가 나는 이유는 buffer 사용 여부의 차이이다.

Scanner 는 1 KB 크기의 버퍼를 갖기 때문에 입력이 바로 전달되는 반면 BufferedReader는 8KB 크기의 버퍼를 가져

buffer에 입력들을 저장하였다가 한 번에 전송하기 때문에 속도가 더 빠르다.

 

또한 Scanner 는 입력을 읽는 과정에서 내부에서 정규 표현식 적용, 입력값 분할, 파싱 등을 거치기 때문에 더욱 느리다. 

 

BufferedReader 사용법

: 버퍼리더같은 경우는 한 줄 읽어서 String으로 가져온다. 그렇기 때문에 Scanner처럼 띄어쓴다고 구분되어서 입력 되는 것이 아니다.

한줄에서 띄어 쓸거면 split으로 구분해줘야 한다.

 

=> 추가적인 내용은 따로 블로그 정리 !

 

 

stream()

 

arr[i] = Arrays.asList(tmp[i].split(""))
                    .stream().mapToInt(Integer::parseInt).toArray();

 

-> 이 문법의 의미는 문자열 배열을 퍼트린 뒤, Inteter.parseInt로 각각 Integer로 바꾼 뒤 다시 toArray 배열로 만든다.

 

이것에 대한 내용도 따로 정리가 필요하다.

 

 

블로그의 프로필 사진

블로그의 정보

DevSecOps

개발하는지호

활동하기

티스토리툴바