[백준 18808] 스티커 붙이기(자바)_강의

안녕하세요 여러분 오늘은 백준 18808 스티커 붙이기를 자바로 풀이해보도록 하겠습니다 ㅎㅎ

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

18808번: 스티커 붙이기

---

구현 문제가 으레 그러하듯, 뭘 구현해야할지 그리고 어떤 흐름으로 짤건지 생각해보시면 됩니다. 

 

우선 짤 거는 두 가지겠죠?

 

1, 스티커를 붙일 수 있는지 확인해주는 함수(붙일 수 있다면 붙이기까지 해주기) >> postatble()

2, 스티커를 회전시키는 함수. >> rotate()

 

 

우선 postable() 함수부터 보면요, 

스티커를 붙일 수 있는지 확인하려면 

이중 for 문으로 확인해주면 되겠죠?? 스티커값이 1인데 노트북값도 1이면 못붙인다 이런 로직으로 짜시면 됩니다.

그 후에 붙일 수 있으면 스티커의 인덱스 i, j 에서 1이면 노트북 x + i, y + j 에 1을 넣어주면 됩니다. (즉, 스티커 붙이기)

 

그리고 그 다음으로 rotate() 함수를 보면요, 배열돌리기 문제를 풀어보신 분이라면 금방 알았을것 같은데요,

 

이럴때는 당황하지 말고 직접 써보면서 규칙을 찾아낸다 라고 생각하시면 편합니다. 

 

rotate() 로직

이 때 B의 행 성분이 그대로 A의 열 성분이 된다는건 규칙에서도 쉽게 드러나니 잘 알수 있겠죠?

문제는 행 성분인데 여기서 한 개 아이디어를 하나 추천해드리면요, 제가 자주 쓰는 테크닉인데요.

지금 열 성분은 알았으니 행 성분이 어떻게 되는지 궁금한거니까 i를 과감하게 0으로 고정시켜놓고 생각해봅시다.

사고과정을 그림에 적어놨으니 잘 따라 할 수 있겠죠??

 

이제 나머지는 틀 정도이니 개인 스타일로 잘 구현하시면 됩니다!

코드나갑니다!!!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m, k;
    static int[][] note = new int[42][42];
    static int r, c; // 이렇게 전역변수로 저장해놓기 그냥.
    static int[][] paper = new int[12][12]; // 스티커 클래스 만들 필요가 없죠?

    //클래스로 만들어서 헤비하게 다니지말고 그때그때 필요한 부분만 사용. 굳이 스티커 정보를 다 저장하고 다닐 필요가없음.
    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());

        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            for (int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < c; j++) {
                    paper[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            //붙이면 다음으로 넘어가야됨 못붙이면 90도 돌리기.
            check :
            for (int rot = 0; rot < 4; rot++) {
                for (int x = 0; x <= n - r; x++) { // n = 7, r = 5인 상황 상상가능.
                    for (int y = 0; y <= m - c; y++) {
                        if (postable(x, y)) {
                            break check;
                        }
                    }
                }
                rotate(); // rot = 3 일때 rotate 실행시키면 안되지만 복잡도 그렇게 크게 증가 x
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count += note[i][j];
            }
        }
        System.out.println(count);
    }

    static boolean postable(int x, int y) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (note[x + i][y + j] == 1 && paper[i][j] == 1) {
                    return false;
                }
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (paper[i][j] == 1) {
                    note[x + i][y + j] = 1;
                }
            }
        }
        return true;
    }

    static void rotate() {
        int[][] temp = new int[12][12];

        for (int i = 0; i < r; i++) System.arraycopy(paper[i], 0, temp[i], 0, c);

        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                paper[i][j] = temp[r - 1 - j][i];
            }
        }
        int tmp = r;
        r = c;
        c = tmp;
    }
}

 

눈여겨 볼 점을 뽑아드리자면요..

 

1, Line 7 ~ 10

제가 처음 풀때는 sticker 정보를 사용자정의 클래스에 담아서 row, col, 모양정보를 저장한 배열을 들고다녔는데요,

그렇게 할 필요 없이 전역변수 느낌으로 가면 편합니다. 그때그때 작업해준다는 느낌?

 

2, Line 37

자바만의 기능이죠 ㅎㅎ!!

for문 바깥에 " 루프명 : " 이런식으로 이중for문이든 삼중for문이든 for문에 루프이름을 붙일 수 있고,

그냥 break 하는것보다 break 루프명 이런식으로 적어서 이중for문 전체를 끝내버릴수 있습니다!

 

3, Line 41

여기서 사실 마지막 i일때 rotate()를 굳이 실행시키지 않아도 되지만, 시간복잡도 측면에서 크게 상관이 없어 그냥 넣었습니다.

 

4, Line 47

굳이 if(note[i][j] == 1) count++ 하지말고 어차피 note[i][j]값이 1이니까 그냥 47번째줄처럼 적어도 되겠죠?

 

5, Line 74

여기서 이중 for문으로 배열 복사하는것도 괜찮은데 개인적으로 내장함수 쓰는걸 좋아하는 편이라 System.arraycopy() 를 써봤습니다 ㅎㅎ 코드도 간결해지고 좋아요~

 

 

감사합니다~~다음편에 뵐게요!