[코드트리/IL] 떨어지는 1자 블록 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 시뮬레이션

1부터 n행까지 돌며 해당 행의 (k, k +m)열의 위치의 값이 모두 0이라면, 다음 행에 넣도록 넘어간다. 모두 0이 아니라면, 해당 행의 바로 위쪽 행에 블록을 넣는다.

 

 

💥 유의사항

마지막 행(n)까지 왔을 때는, 마지막 행의 (k, k+m) 위치의 값이 모두 0이라면 마지막 열에 블록을 두고, 0이 아니라면 바로 윗 행에 블록을 두도록 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n,m,k;
    static int[][] grid;
 
    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());   // 블록 크기
        k = Integer.parseInt(st.nextToken());   // 블록 떨어질 위치
 
        grid = new int[n+1][n+1];
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= n ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int row = 1;
        while(true) {
            if(row == n) { // 마지막 행까지 왔을 때
                if(!allZero(row))    // 블록 범위 내 값들이 모두 0이 아니라면, 바로 위 행에 블록 두기
                    putBlocks(row - 1);
                else    // 모두 0이라면, 해당 행에 블록 두기
                    putBlocks(row);
 
                break;
            }
 
            if(allZero(row)) {    // 모두 0이라면, 다음 행 확인하러 넘어가기
                row++;
            }
            else {  // 모두 0이 아니라면, 바로 윗 줄에 블록 두기               
                putBlocks(row - 1);
                break;
            }
        }
 
        print();
    }
 
    // 모두 0인지 확인하는 메서드
    private static boolean allZero(int row) {
        for(int col = k ; col < k + m ; col++) {
            if(grid[row][col] != 0)
                return false;
        }
 
        return true;
    }
 
    // 블럭 두는 메서드
    private static void putBlocks(int row) {
        for(int col = k ; col < k + m ; col++) {
            grid[row][col] = 1;
        }
    }
 
    // 출력 메서드
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++)
                sb.append(grid[i][j]).append(" ");
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

 

➕ 다른 풀이 방식

(126ms, 10MB)

import java.util.*;
import java.io.*;
 
public class Main {
    static int n,m,k;
    static int[][] grid;
 
    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());   // 블록 크기
        k = Integer.parseInt(st.nextToken());   // 블록 떨어질 위치
 
        grid = new int[n+1][n+1];
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= n ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 1. 최종적으로 멈추게 될 위치를 구한다.
        int targetRow = getTargetRow(); 
        
        // 2. 최종 위치에 전부 블록을 표시한다.
        putBlocks(targetRow);
 
        // 3. 출력한다.
        print();
    }
    
    // 최종적으로 멈추게 될 위치 구하는 메소드
    private static int getTargetRow() {
        for(int row = 1 ; row <= n ; row++) {
            if(!allZero(row))
                return row - 1;
        }
        
        return n;
    }
 
    // 모두 0인지 확인하는 메서드
    private static boolean allZero(int row) {
        for(int col = k ; col < k + m ; col++) {
            if(grid[row][col] != 0)
                return false;
        }
 
        return true;
    }
 
    // 블럭 두는 메서드
    private static void putBlocks(int row) {
        for(int col = k ; col < k + m ; col++) {
            grid[row][col] = 1;
        }
    }
 
    // 출력 메서드
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++)
                sb.append(grid[i][j]).append(" ");
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

 

---

💦 어려웠던 점

마지막 행까지 왔을 때 처리를 제대로 하지 않아 좀 헤맸다.

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리