[Java/구현] 백준 18808. 스티커 붙이기

🤔 Intuition

딱 봐도 단순 구현으로 보였다. 시간복잡도가 들어오는지 계산해봤는데, 시간제한이 2초인 데다가 1초 이내로도 충분히 끊어낼 것으로 봐서 단순 구현으로 풀었다.

🔎 Algorithm & Complexity

* @algorithm implementation
* @time O(N*M*K*R*C) : 노트북 위 탐색기준좌표 O(N*M) * 스티커 개수 O(K) * 스티커 크기만큼 탐색 O(R*C) -> 188ms
* @memory O(N*M + R*C) : 노트북 배열 O(N*M) + 스티커 배열 (R*C) -> 16204 KB

👨🏻‍💻 Logic

하라는 대로 하면 된다.

1. 스티커를 입력받고

2. 노트북에 스티커를 붙일 수 있는지 체크하고 (조건에 따라 좌상부터 우하 방향으로 진행)

3. 가능하면 붙이고 다음 스티커를 보면 된다. 못붙이면 돌려서 붙여본다.

 

위 과정을 코드로 나타내면 다음과 같다.

public class BOJ_18808_스티커붙이기 {
    private static int ans;
    private static int N, M, K, R, C;
    private static int[][] map; // 노트북
    private static int[][] sticker; // 기본 스티커
    private static int turnCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            sticker = new int[R][C];

            for (int j = 0; j < R; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < C; k++) {
                    sticker[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            turnCnt = 0;
            int y;
            int x;
            do {
                y = turnCnt % 2 == 0 ? R : C;
                x = turnCnt % 2 == 0 ? C : R;
                stick(y, x);
            } while (turn(y, x));
        }


        br.close();
        bw.write(sb.append(ans).toString());
        bw.flush();
        bw.close();
    }

    private static void stick(int y, int x) {
        for (int i = 0; i < N - y + 1; i++) {
            top:
            for (int j = 0; j < M - x + 1; j++) {
                // 기준 좌표 설정

                for (int k = 0; k < y; k++) {
                    for (int l = 0; l < x; l++) {
                        if (sticker[k][l] == 1 && map[i + k][j + l] == 1) {
                            continue top; // 다음 좌표 탐색
                        }
                    }
                }

                for (int k = 0; k < y; k++) {
                    for (int l = 0; l < x; l++) {
                        if (sticker[k][l] == 1) {
                            map[i + k][j + l] = sticker[k][l];
                            ans++;
                        }
                    }
                }
                turnCnt = 3; // 끝내기
                return;
            }
        }
    }
    private static boolean turn(int y, int x) {
        if (turnCnt == 3) {
            return false;
        }
        turnCnt++;


        // 배열 돌리기
        int[][] temp = new int[x][y];
        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                temp[j][y - i - 1] = sticker[i][j];
            }
        }

        sticker = new int[x][y];
        for (int i = 0; i < x; i++) {
            sticker[i] = temp[i].clone();
        }



        return true;
    }

}