2019 카카오 블라인드 코딩테스트 - 블록 게임 (feat. Java)

2020. 5. 17. 13:18· 알고리즘/연습문제
목차
  1. 문제 정보는 아래 링크를 확인해주세요!
  2. [블록 게임]
반응형

문제 정보는 아래 링크를 확인해주세요!

[블록 게임]

 

코딩테스트 연습 - 블록 게임

[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2

programmers.co.kr

문제 접근 방법

  • 검은색 블록을 놓을 수 있는 도형은 2x3과 3x2 이 두개의 직사각형 범위 안에서 확인이 가능하고,
  • 수평으로 긴 직사각형 안에서는 윗칸의 2개의 값이 비어있어야 가능
  • 수직으로 긴 직사각형 안에서는 오른쪽과 왼쪽중 한쪽의 블록이 2개가 비어있어야 가능
  • 블록 검사는 맵의 왼쪽부터 오른쪽 컬럼까지 한칸씩 이동하며
  • 해당 칸의 비어있지 않은 맨 위에 있는 칸부터 시작한다.
  • 수평 검사와 수직 검사에 대한 자세한 설명은 아래 그림 참조!

그림 설명

[소스 코드]

package algorithm.programmers;

import java.util.*;

/*
 * 2019 카카오 블라인드
 * 블록 게임
 *
 * */
public class Pro42894 {
    private static int[][] board;//게임 맵
    private static int[] maxRow;//해당 구간중 가장 위에 있는 row 값
    private static int len;

    //블록의 좌표
    private static class Dot {
        int x;
        int y;

        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


    public static int solution(int[][] Board) {
        int answer = 0;

        board = Board;
        len = board.length;

        maxRow = new int[len];

        //각 column당 가장 높은 값을 담는다.
        for (int i = 0; i < len; i++) setMaxRow(i);

        int cnt = 1;

        while(cnt>0) {//지울 수 있는 블록이 1개보다 많을 때까지

            cnt = 0;

            //각 column을 기준으로 수평블록인지 수직블록인지 검사한다.
            for (int i = 0; i < len; i++) {

                cnt += checkHorizon(i);
                cnt += checkVertical(i);
            }

            answer += cnt;//지워준 블록의 갯수를 결과 값에 추가
        }

        return answer;
    }

    //수직으로 긴 블록을 검사
    private static int checkVertical(int col) {

        if (col+1 >= len) return 0;//현재 컬럼 기준 +1 위치가 맵 밖이라면 종료

        int maxR = Math.max(maxRow[col], maxRow[col+1]);//현재컬럼과 현재컬럼+1블록 중 가장 위에있는 블록

        if (maxR-2<0 || maxR>=len) return 0;//수직블록이므로 row가 현재기준 -2보다 작거나 maxR이 맵 범위 밖에있으면 안된다.

        int zero 	= 0;//비어있는 블록을 검사
        int block	= board[maxR][col];//현재 가장 위에있는 블록의 값

        ArrayList<Dot> remove = new ArrayList<>();//지워줄 리스트

        for (int i = maxR-2; i <= maxR; i++) {//수직블록은 위로 3개를 검사하므로

            for (int j = col; j <= col+1; j++) {//수직블록은 옆으로 2개를 검사하므로

                if (board[i][j] != 0 && board[i][j] != block) return 0;//0이 아니면서 현재 블록 값과 다를 때,

                if (board[i][j] == 0) zero++;//비어있는 블록을 추가
                else remove.add(new Dot(i,j));//지워줄 리스트에 블록 위치 추가
            }
        }

        if (zero != 2) return 0;//수직 블록의 비어있는 값이 2개 일 때, 지워줄 수 있다.

        for (Dot d : remove) board[d.x][d.y] = 0;//현재 지워지는 블록들의 위치를 0으로 만든다.

        setMaxRow(col);//현재 블록들의 maxR을 재설정
        setMaxRow(col+1);

        return 1;//하나의 블록을 지웠으므로 1 리턴
    }

    //수평 블록
    private static int checkHorizon(int col) {

        if (col+2 >= len) return 0;//수평 블록은 옆으로 3개를 검사하므로

        int row1 = maxRow[col];
        int row2 = maxRow[col+1];
        int row3 = maxRow[col+2];

        int maxR = Math.max(row1, Math.max(row2, row3));//3개의 column중 가장 위에 있는 row를 확인

        int sameRow = 0;//수평 블록은 같은 row가 2개가 있으므로 이를 검사하기 위함

        if (row1 == maxR) sameRow++;
        if (row2 == maxR) sameRow++;
        if (row3 == maxR) sameRow++;

        if (sameRow != 2 || maxR-1 < 0 || maxR >= len) return 0;//같은 블록이 2개가 아니거나, maxR이 범위 밖일 경우 종료

        int zero 	= 0;
        int block	= board[maxR][col];

        ArrayList<Dot> remove = new ArrayList<>();

        for (int i = maxR-1; i <= maxR; i++) {//수평블록은 위로 2개를 검사

            for (int j = col; j <= col+2; j++) {//수평블록은 옆으로 3개를 검사

                if (board[i][j] != 0 && board[i][j] != block) return 0;

                if (board[i][j] == 0) zero++;
                else remove.add(new Dot(i,j));
            }
        }

        if (zero != 2) return 0;

        for (Dot d : remove) board[d.x][d.y] = 0;

        setMaxRow(col);
        setMaxRow(col+1);
        setMaxRow(col+2);

        return 1;
    }

    //maxR을 구하는 메서드
    private static void setMaxRow(int col) {

        int i = 0;

        for (i = 0; i < len; i++) {//map의 해당 컬럼의 제일 위부터 0이 아닌 값이 나올 때까지 검사

            if (board[i][col] != 0) break;
        }

        maxRow[col] = i;//0이 아닌 값이 나왔을 때, 해당 인덱스를 maxR에 저장
    }
}

 

[정확성 테스트]

 

반응형
LIST

'알고리즘 > 연습문제' 카테고리의 다른 글

2020 카카오 블라인드 코딩테스트 - 괄호 변환 (feat. Java)  (0) 2020.05.19
2020 카카오 블라인드 코딩테스트 - 문자열 압축 (feat. Java)  (0) 2020.05.19
2019 카카오 블라인드 코딩테스트 - 매칭 점수 (fea. Java)  (1) 2020.05.16
2019 카카오 블라인드 코딩테스트 - 길 찾기 게임 (feat. Java)  (0) 2020.05.16
2019 카카오 블라인드 코딩테스트 - 무지의 먹방 라이브 (feat. Java)  (0) 2020.05.15
  1. 문제 정보는 아래 링크를 확인해주세요!
  2. [블록 게임]
'알고리즘/연습문제' 카테고리의 다른 글
  • 2020 카카오 블라인드 코딩테스트 - 괄호 변환 (feat. Java)
  • 2020 카카오 블라인드 코딩테스트 - 문자열 압축 (feat. Java)
  • 2019 카카오 블라인드 코딩테스트 - 매칭 점수 (fea. Java)
  • 2019 카카오 블라인드 코딩테스트 - 길 찾기 게임 (feat. Java)
iron_jin
iron_jin
배운 것에 대한 내 생각을 가지고 정리하자
學而不思則罔(학이불사즉망)배운 것에 대한 내 생각을 가지고 정리하자
iron_jin
學而不思則罔(학이불사즉망)
iron_jin
전체
오늘
어제
  • 전체 (163)
    • 도서 (10)
    • 생각 정리 (0)
    • 후기 모음 (14)
    • 언어 (20)
      • css (1)
      • java (9)
      • Kotlin (0)
      • javascript (0)
      • Solidity (3)
      • Python (3)
      • GO (3)
      • C++ (1)
    • Spring Framework (32)
      • spring (16)
      • JPA (6)
      • Error (4)
      • Settings (4)
    • 알고리즘 (62)
      • 이론 (0)
      • 연습문제 (58)
    • 인프라 (6)
      • 클라우드 (1)
      • 도커 (0)
      • AWS (4)
      • Elastic Search (0)
    • 쿠버네티스 (3)
      • 이론 (0)
      • 실습 (2)
      • 트러블슈팅 (1)
    • Nginx (2)
    • CS (4)
      • 서버 (0)
      • 리눅스 (2)
      • 네트워크 (0)
      • OAuth (2)
    • 형상관리 (3)
      • GIT (3)
    • Open API (3)
      • 카카오 API (1)
      • QGIS (2)
    • 보안 (0)
      • 알고리즘 (0)
    • 공통 (1)
      • 성능 관리 도구 (1)
    • Database (2)
      • MySQL (1)
      • Redis (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Java
  • 2018 kakao
  • 항해플러스
  • 2019 카카오 블라인드
  • 2020 kakao
  • 백준
  • 카카오 겨울 인턴십
  • 자바
  • 프로그래머스
  • 도메인 주도 개발
  • ddd
  • MySQL
  • 스프링 부트
  • 항해99
  • JPA
  • spring
  • AWS
  • Python
  • 2020 카카오 블라인드
  • 알고리즘
  • Hibernate
  • SpringBoot
  • 2020 카카오
  • 코딩테스트
  • spring boot
  • 2018 카카오 블라인드
  • 2019 카카오
  • 에릭 에반스
  • 스프링
  • 2019 kakao

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
iron_jin
2019 카카오 블라인드 코딩테스트 - 블록 게임 (feat. Java)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.