๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algorithm

๐Ÿค” 2020 ์นด์นด์˜ค ๋ธ”๋ผ์ธ๋“œ ๊ณต์ฑ„: ์ž๋ฌผ์‡ ์™€ ์—ด์‡  (Java)

๐Ÿ“Œ ๋ฌธ์ œ

๊ณ ๊ณ ํ•™์ž์ธ ํŠœ๋ธŒ๋Š” ๊ณ ๋Œ€ ์œ ์ ์ง€์—์„œ ๋ณด๋ฌผ๊ณผ ์œ ์ ์ด ๊ฐ€๋“ํ•  ๊ฒƒ์œผ๋กœ ์ถ”์ •๋˜๋Š” ๋น„๋ฐ€์˜ ๋ฌธ์„ ๋ฐœ๊ฒฌํ•˜์˜€์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋ฌธ์„ ์—ด๋ ค๊ณ  ์‚ดํŽด๋ณด๋‹ˆ ํŠน์ดํ•œ ํ˜•ํƒœ์˜ ์ž๋ฌผ์‡ ๋กœ ์ž ๊ฒจ ์žˆ์—ˆ๊ณ  ๋ฌธ ์•ž์—๋Š” ํŠน์ดํ•œ ํ˜•ํƒœ์˜ ์—ด์‡ ์™€ ํ•จ๊ป˜ ์ž๋ฌผ์‡ ๋ฅผ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ค๋ช…ํ•ด ์ฃผ๋Š” ์ข…์ด๊ฐ€ ๋ฐœ๊ฒฌ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

์ž ๊ฒจ์žˆ๋Š” ์ž๋ฌผ์‡ ๋Š” ๊ฒฉ์ž ํ•œ ์นธ์˜ ํฌ๊ธฐ๊ฐ€ 1 x 1์ธ N x N ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐ ๊ฒฉ์ž ํ˜•ํƒœ์ด๊ณ  ํŠน์ดํ•œ ๋ชจ์–‘์˜ ์—ด์‡ ๋Š” M x M ํฌ๊ธฐ์ธ ์ •์‚ฌ๊ฐ ๊ฒฉ์ž ํ˜•ํƒœ๋กœ ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ž๋ฌผ์‡ ์—๋Š” ํ™ˆ์ด ํŒŒ์—ฌ ์žˆ๊ณ  ์—ด์‡  ๋˜ํ•œ ํ™ˆ๊ณผ ๋Œ๊ธฐ ๋ถ€๋ถ„์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์—ด์‡ ๋Š” ํšŒ์ „๊ณผ ์ด๋™์ด ๊ฐ€๋Šฅํ•˜๋ฉฐ ์—ด์‡ ์˜ ๋Œ๊ธฐ ๋ถ€๋ถ„์„ ์ž๋ฌผ์‡ ์˜ ํ™ˆ ๋ถ€๋ถ„์— ๋”ฑ ๋งž๊ฒŒ ์ฑ„์šฐ๋ฉด ์ž๋ฌผ์‡ ๊ฐ€ ์—ด๋ฆฌ๊ฒŒ ๋˜๋Š” ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ž๋ฌผ์‡  ์˜์—ญ์„ ๋ฒ—์–ด๋‚œ ๋ถ€๋ถ„์— ์žˆ๋Š” ์—ด์‡ ์˜ ํ™ˆ๊ณผ ๋Œ๊ธฐ๋Š” ์ž๋ฌผ์‡ ๋ฅผ ์—ฌ๋Š” ๋ฐ ์˜ํ–ฅ์„ ์ฃผ์ง€ ์•Š์ง€๋งŒ, ์ž๋ฌผ์‡  ์˜์—ญ ๋‚ด์—์„œ๋Š” ์—ด์‡ ์˜ ๋Œ๊ธฐ ๋ถ€๋ถ„๊ณผ ์ž๋ฌผ์‡ ์˜ ํ™ˆ ๋ถ€๋ถ„์ด ์ •ํ™•ํžˆ ์ผ์น˜ํ•ด์•ผ ํ•˜๋ฉฐ ์—ด์‡ ์˜ ๋Œ๊ธฐ์™€ ์ž๋ฌผ์‡ ์˜ ๋Œ๊ธฐ๊ฐ€ ๋งŒ๋‚˜์„œ๋Š” ์•ˆ๋ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ ์ž๋ฌผ์‡ ์˜ ๋ชจ๋“  ํ™ˆ์„ ์ฑ„์›Œ ๋น„์–ด์žˆ๋Š” ๊ณณ์ด ์—†์–ด์•ผ ์ž๋ฌผ์‡ ๋ฅผ ์—ด ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์—ด์‡ ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” 2์ฐจ์› ๋ฐฐ์—ด key์™€ ์ž๋ฌผ์‡ ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” 2์ฐจ์› ๋ฐฐ์—ด lock์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์—ด์‡ ๋กœ ์ž๋ฌผ์‡ ๋ฅผ ์—ด์ˆ˜ ์žˆ์œผ๋ฉด true๋ฅผ, ์—ด ์ˆ˜ ์—†์œผ๋ฉด false๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

๐Ÿ“Œ ์ œํ•œ์‚ฌํ•ญ

  • key๋Š” M x M(3 ≤ M ≤ 20, M์€ ์ž์—ฐ์ˆ˜)ํฌ๊ธฐ 2์ฐจ์› ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.
  • lock์€ N x N(3 ≤ N ≤ 20, N์€ ์ž์—ฐ์ˆ˜)ํฌ๊ธฐ 2์ฐจ์› ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.
  • M์€ ํ•ญ์ƒ N ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • key์™€ lock์˜ ์›์†Œ๋Š” 0 ๋˜๋Š” 1๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
    • 0์€ ํ™ˆ ๋ถ€๋ถ„, 1์€ ๋Œ๊ธฐ ๋ถ€๋ถ„์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.

๐Ÿ“Œ ํ’€์ด

ํฌ๊ฒŒ 3๊ฐ€์ง€ ๊ธฐ๋Šฅ์„ ๋งŒ๋“ค๋ฉด ๋˜๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

1. lock์„ 3๋ฐฐ๋กœ ๋Š˜๋ฆฌ๊ธฐ
lock์„ 3๋ฐฐ๋กœ ๋Š˜๋ฆฌ๋ฉด์„œ, ์‹ค์ œ lock์— ํ•ด๋‹นํ•˜์ง€ ์•Š๋Š” ๊ฐ’์€ 3์œผ๋กœ ์„ค์ •ํ•ด์คฌ๋‹ค. (๋‚˜์ค‘์— ๊ณ„์‚ฐํ•  ๋•Œ, ๋ฌด์‹œํ•˜๊ธฐ ์œ„ํ•จ)
ํ™ˆ์„ ๋ฐœ๊ฒฌํ•˜๋ฉด count++ (count๋Š” lock์˜ ํ™ˆ์˜ ๊ฐœ์ˆ˜๋ฅผ ์˜๋ฏธ)

2. ๋ชจ๋“  ํ™ˆ์ด ์ฑ„์›Œ์กŒ๋Š”์ง€ ํ™•์ธ
- ์‹ค์ œ lock์— ํ•ด๋‹นํ•˜์ง€ ์•Š๋Š” ๊ฐ’(3)์€ ๋ฌด์‹œ.
- lock๊ณผ key ๋ชจ๋‘ ๋Œ๊ธฐ๋ผ๋ฉด ์ž๋ฌผ์‡ ๋ฅผ ํ’€ ์ˆ˜ ์—†๋‹ค๋Š” ๊ฒƒ.
- lock์ด ํ™ˆ์ด๊ณ , key๊ฐ€ ๋Œ๊ธฐ๋ฉด ํ™ˆ์ด ์ฑ„์›Œ์กŒ๋‹ค๋Š” ์˜๋ฏธ๋กœ tempCount++
์‹ค์ œ lock์˜ ํ™ˆ์˜ ๊ฐœ์ˆ˜(count)์™€ ์ฑ„์›Œ์ง„ ํ™ˆ์˜ ๊ฐœ์ˆ˜(tempCount)๊ฐ€ ๊ฐ™์œผ๋ฉด, ํ•ด๋‹น ์—ด์‡ ๋กœ ์ž๋ฌผ์‡ ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ.

3. key ๋ฐฐ์—ด ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ 90๋„ ๋Œ๋ฆฌ๊ธฐ
์ด 4๋ฒˆ ๋Œ๋ฆฐ๋‹ค. (0๋„, 90๋„, 180๋„, 270๋„)
5๋ฒˆ์งธ๋Š” 360๋„๋กœ 0๋„์™€ ๊ฐ™์€ ๊ฐ’์ด๋ผ์„œ ๋Œ๋ฆฌ์ง€ ์•Š๋Š”๋‹ค.

๐Ÿ“Œ ์ฝ”๋“œ

public class ์ž๋ฌผ์‡ ์™€์—ด์‡  {

    int count;
    
    public boolean solution(int[][] key, int[][] lock) {
        this.count = 0;
        lock = initLock(lock);
        for (int i = 0; i < 4; i++) {
            if (isMatch(key, lock)) return true;
            key = rotation(key);
        }
        return false;
    }

    private int[][] initLock(int[][] lock) {
        int n = lock.length;
        int[][] result = new int[n * 3][n * 3];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result.length; j++) {
                if (i >= n && i < n * 2 && j >= n && j < n * 2) {
                    result[i][j] = lock[i - n][j - n];
                    if (result[i][j] == 0) this.count++;
                } else {
                    result[i][j] = 3;
                }
            }
        }
        return result;
    }

    private boolean isMatch(int[][] key, int[][] lock) {
        int keySize = key.length;
        int lockSize = lock.length;

        for (int i = 0; i <= lockSize - keySize; i++) {
            for (int j = 0; j <= lockSize - keySize; j++) {
                if (isMatch(key, lock, i, j)) return true;
            }
        }
        return false;
    }

    private boolean isMatch(int[][] key, int[][] lock, int x, int y) {
        int n = key.length;
        int tempCount = 0;
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (lock[i][j] == 3) continue;
                if (lock[i][j] == 1 && key[i - x][j - y] == 1) return false;
                if (lock[i][j] == 0 && key[i - x][j - y] == 1) tempCount++;
            }
        }
        return count ==  tempCount;
    }

    private int[][] rotation(int[][] key) {
        int n = key.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = key[n - 1 - j][i];
            }
        }
        return result;
    }
}