쵼쥬
쵼쥬의 개발공부 TIL
쵼쥬
전체 방문자
오늘
어제
  • 분류 전체보기 (276)
    • 코딩테스트 (192)
      • [알고리즘] 알고리즘 정리 (7)
      • [백준] 코딩테스트 연습 (126)
      • [프로그래머스] 코딩테스트 연습 (59)
    • Spring (71)
      • [인프런] 스프링 핵심 원리- 기본편 (9)
      • [인프런] 스프링 MVC 1 (6)
      • [인프런] 스프링 MVC 2 (4)
      • [인프런] 실전! 스프링 부트와 JPA 활용1 (7)
      • [인프런] 실전! 스프링 부트와 JPA 활용2 (5)
      • [인프런] 실전! 스프링 데이터 JPA (7)
      • [인프런] 실전! Querydsl (7)
      • JWT (5)
      • [인프런] Spring Cloud (17)
      • [인프런] Spring Batch (4)
    • Java (6)
      • [Java8] 모던인자바액션 (4)
      • [부스트코스] 웹 백엔드 (2)
      • [패스트캠퍼스] JAVA STREAM (0)
    • CS (6)
      • 디자인 패턴과 프로그래밍 패터다임 (2)
      • 네트워크 (4)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • 부스트코스
  • 비트마스킹
  • 구현
  • 위클리 챌린지
  • BFS
  • 알고리즘
  • 스프링
  • spring
  • 인프런
  • 백준
  • querydsl
  • 코딩테스트
  • 자바
  • 타임리프
  • 백분
  • Spring Data JPA
  • jpa
  • MVC
  • 프로그래머스
  • 누적합

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
쵼쥬

쵼쥬의 개발공부 TIL

십자가 2개 놓기 - 17085번
코딩테스트/[백준] 코딩테스트 연습

십자가 2개 놓기 - 17085번

2021. 11. 5. 14:32


풀이 방법

격자판의 크기가 크지 않아서 완전탐색을 이용했다.

max값을 만들 수 있는 모든 십자가의 넓이를 비교해서 max 값을 처음 정해서 넓이가 1인 경우는 제외했다.

list에 만들 수 있는 십자가가 차이자는 위치를 넣어주고 십자가가 겹치지 않는 경우에 넓이 곱의 최댓값을 구해주었다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static String[][] arr;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new String[N + 2][M + 2];

        for (int i = 0; i < N + 2; i++) {
            Arrays.fill(arr[i], ".");
        }

        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = s.charAt(j - 1) + "";
            }
        }

        int index = -1;
        int max = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j].equals("."))
                    continue;
                int x = 1;

                while (true) {
                    if (arr[i + x][j].equals("#")
                            && arr[i - x][j].equals("#")
                            && arr[i][j + x].equals("#")
                            && arr[i][j - x].equals("#")) {
                        list.add(new ArrayList<>());
                        index++;
                        list.get(index).add(new int[]{i, j});

                        for (int k = 1; k <= x; k++) {
                            list.get(index).add(new int[]{i + k, j});
                            list.get(index).add(new int[]{i - k, j});
                            list.get(index).add(new int[]{i, j + k});
                            list.get(index).add(new int[]{i, j - k});
                        }
                        max = Math.max(list.get(index).size(), max);
                        x++;
                    } else break;
                }
            }
        }

        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                boolean check = true;

                for (int k = 0; k < list.get(i).size(); k++) {
                    for (int v = 0; v < list.get(j).size(); v++) {
                        if(list.get(i).get(k)[0] == list.get(j).get(v)[0]
                                && list.get(i).get(k)[1] == list.get(j).get(v)[1]){
                            check = false;
                            break;
                        }
                    }
                    if(!check)
                        break;
                }

                if(check)
                    max = Math.max(list.get(i).size() * list.get(j).size(), max);
            }
        }
        System.out.println(max);
    }
}

'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글

팀 배정 - 18768번  (0) 2021.11.08
거짓말 - 1043번  (0) 2021.11.08
Coins - 3067번  (0) 2021.11.04
뱀 - 3190번  (0) 2021.11.02
A -> B - 16953번  (0) 2021.11.02
    '코딩테스트/[백준] 코딩테스트 연습' 카테고리의 다른 글
    • 팀 배정 - 18768번
    • 거짓말 - 1043번
    • Coins - 3067번
    • 뱀 - 3190번
    쵼쥬
    쵼쥬

    티스토리툴바