#hackerrank#The Grid Search#algorithm#알고리즘

problem link : 

https://www.hackerrank.com/challenges/the-grid-search/problem

 

The Grid Search | HackerRank

 

The Grid Search | HackerRank

 

* 해결 전략

1) 탐색 공간을 정함 (0 <= y <= R-r, 0 <= x <= C-c)

2) G와 P를 비교해서 다른 게 있으면 return

3) O(RCrc) = O(1000^4)

중간에 return 되는 경우가 많아서 괜찮은 것 같음.

 

* source code

static boolean match(String[] G, String[] P, int r, int c, int y, int x) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (G[y + i].charAt(x + j) != P[i].charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }

    // Complete the gridSearch function below.
    static String gridSearch(String[] G, String[] P) {
        int R = G.length;
        int C = G[0].length();
        int r = P.length;
        int c = P[0].length();

        for (int i = 0; i <= R - r; i++) {
            for (int j = 0; j <= C - c; j++) {
                if (match(G, P, r, c, i, j)) {
                    return "YES";
                }
            }
        }
        return "NO";
    }

 

The Grid Search | HackerRank