TigerCow.Door

안녕하세요 .문범우입니다.

이번 포스팅에서는 hackerrank의 The Grid Search 문제를 풀어보았습니다.

난이도는 Medium, rate는 약 75%입니다.

문제 개념이나 이해자체는 크게 어렵지 않다고 생각되나 몇가지 고려할 부분들이 존재합니다.


제가 중요시 생각한 점은,

먼저 탐색하고자 하는 P배열에 대해 그 첫번째 행이 G배열에서 존재할때만 실질적인 탐색문을 반복하는 것과

그 첫번째 행이 G배열의 특정행에서 반복하여 존재할 수 있기 때문에 인덱스를 고려해가며 탐색하는 것 입니다.


보다 자세한 설명은 코드에 주석으로 달아 놓았습니다.

궁금하시거나 코드를 보다 효율적으로 개선할 방법에 대해서는 댓글 및 카카오톡, 이메일을 통해 말씀해주시면 감사하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the gridSearch function below.
    static String gridSearch(String[] G, String[] P) {
        // G를 입력배열, P를 목표배열이라 하겠음
        int G_width = G[0].length(); // 입력배열의 가로길이 -> 목표배열 한줄씩 탐색시 사용됨. 
        int G_height = G.length// 입력배열의 세로길이 -> 목표배열 탐색 중에 입력배열의 높이를 넘어가면 NO를 반환
        int P_width = P[0].length(); // 목표배열의 가로길이
        int P_height = P.length// 목표배열의 세로길이 -> 목표배열 탐색 중에 목표배열의 높이를 넘어가면 YES를 반환
        int start_num = -1
        // 탐색중인 목표배열의 1 행이 13일떄, 입력배열에 01300130 과 같이 중복되서 나타날 수 있음
        // 이때 입력배열의 한줄에 대해 각각 검사하기 위해 사용하기도 하며
        // 목표배열의 1행이 위와 같이 13이고, 2행이 27일때, 입력배열이 다음과 같을 수 있음
        // 01300130
        // 99992799
        // 이러한 경우를 위해 각 입력배열의 각줄에 목표배열의 행이 포함되는지 여부뿐아니라,
        // 그 시작 인덱스가 일치하는지 알아야 하기 때문에 이때 start_num이 사용됨
        int count_from = -1;
        int count = 0;
        // count_from과 count변수는 입력배열의 탐색하고자 하는 목표배열의 행에 대해
        // 입력배열의 한 행에 몇개나 같은 문자열이 포함되어있는지를 저장함.
        // 즉, 위와 같이 01300130 같은 경우 count가 2가 되어서
        // 각각에 대해서 탐색을 진행해야 하기 때문에 탐색문을 2번 실행하게함
        for(int j=0;j<G_height;j++){ // 입력배열의 한 행씩 탐색을 진행함
            if(G[j].contains(P[0])){ // 어찌되었는 목표배열의 첫번째 행이 입력배열에 존재할때 탐색을 시작해야함
                count = 0
                start_num = -1;
                // count와 start_num 초기화, count_from은 아래 while문을 통해서 자동적으로 초기화가 됨
                while((count_from = G[j].indexOf(P[0], count_from + 1))>=0){
                    // G[j]에 P[0]가 어느 인덱스에서 시작되는지 확인, 이때 그 뒤에 count_from+1 인자를 줌으로써
                    // G[j]의 count_from+1 인덱스 이후로 부터 확인을 하는 것,
                    // 존재한다면 양수값을 주기때문에 count 값을 하나 증가,
                    // 존재하지 않는다면 -1을 반환하므로 count_from이 초기화 되는 기능이 됨
                    count++;
                }
                // 실질적인 탐색문 시작
                for(int i=0;i<count;i++){
                    start_num = G[j].indexOf(P[0], start_num+1); // G[j]에서 P[0]가 포함된 인덱스를 구함
                    for(int k=0;k<P_height;k++){ // 이제 모든 목표배열행에 대해 탐색할 것
                        if((G[j+k].contains(P[k]))&(start_num == G[j+k].indexOf(P[k],start_num))){
                            // 목표배열의 다음행이 입력배열의 다음행에 포함되어있는지 확인하면서
                            // 그 시작위치가 동일한지 확인 -> else: 즉, 그게 아니면 목표배열의 첫행에 대해 재탐색
                            if(k+1 == P_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가면 모든 목표배열에 대해 탐색이 된 것이므로
                                // YES를 반환
                                return "YES";
                            }else if(j+k+1 == G_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가기 전에 입력배열의 높이를 넘어가면
                                // 입력배열에 목표배열이 완전하게 존재하지 않는 것이기 때문에 NO를 반환
                                return "NO";
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
        } // 해당 for문이 끝난 것은 입력배열에 목표배열이 포함되어 있지 않다는 뜻이기에 NO를 반환함
        return "NO";
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int tItr = 0; tItr < t; tItr++) {
            String[] RC = scanner.nextLine().split(" ");
 
            int R = Integer.parseInt(RC[0]);
 
            int C = Integer.parseInt(RC[1]);
 
            String[] G = new String[R];
 
            for (int i = 0; i < R; i++) {
                String GItem = scanner.nextLine();
                G[i] = GItem;
            }
 
            String[] rc = scanner.nextLine().split(" ");
 
            int r = Integer.parseInt(rc[0]);
 
            int c = Integer.parseInt(rc[1]);
 
            String[] P = new String[r];
 
            for (int i = 0; i < r; i++) {
                String PItem = scanner.nextLine();
                P[i] = PItem;
            }
 
            String result = gridSearch(G, P);
 
            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번에는 Hackerrank의 문제를 풀어보았습니다.

문제 이름은 Lily's Homework이며 Medium 난이도에 속해있습니다.

생각외로 rate가 47% 정도로 좀 낮은편 입니다.

해당 문제는 아래 주소에서 풀어보실 수 있습니다.


https://www.hackerrank.com/challenges/lilys-homework/problem


코드에 주석을 통해 설명을 덧붙여 놓았기 때문에 추가적인 설명은 생략하겠습니다.

해당 코드는 아래 github 주소에서도 확인할 수 있습니다.


https://github.com/doorBW/algorithm_practice


보다 궁금한 점이 있으신 분들은 댓글 및 이메일, 카카오톡을 통해 연락주시면 바로 답변드리도록 하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
    static int lilysHomework(int[] arr) {
        // arr을 오름차순 또는 내림차순의 형태로 만들어야 한다.
        // 그때가 문제에서 말한 cost가 가장 적은 경우기 때문에,
        // 이때 문제는, arr을 오름차순으로 만드는데 필요한 swap횟수와
        // arr을 내림차순으로 만드는데 필요한 swap횟수가 다르다.
        // 따라서 오름차순 및 내림차순 두 방법 모두 시행하고 그 중 작은 값을 반환한다.
 
        int answer_asc = 0;
        int answer_desc = 0;
        int idx,temp;
        int arr_length = arr.length;
        // 기존 arr은 오름차순에서 사용될 것
        // 내림차순에서 사용될 arr_desc을 만들고 기존 arr을 복사해서 넣는다.
        int[] arr_desc = new int[arr_length];
        System.arraycopy( arr, 0, arr_desc, 0, arr_length );
 
        // 오름차순으로 정렬된 sorted_arr
        int[] sorted_arr = new int[arr_length];
        System.arraycopy( arr, 0, sorted_arr, 0, arr_length );
        Arrays.sort(sorted_arr);
        
        // 내림차순으로 정렬된 reversed_arr
        int[] reversed_arr = new int[arr_length];
        for(int i=0;i<arr_length;i++){
            reversed_arr[i] = -1 * arr[i];
        }
        Arrays.sort(reversed_arr);
        for(int i = 0; i < arr_length; i++){
            reversed_arr[i] *= -1;
        }
        
        // 오름차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_asc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_asc.put(arr[i],i);
        }
 
        // 내림차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_desc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_desc.put(arr_desc[i],i);
        }
        
        // 오름차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(sorted_arr[i] != arr[i]){
                idx = idxMap_asc.get(sorted_arr[i]);
                idxMap_asc.put(arr[i],idx);
                temp = arr[i];
                arr[i] = sorted_arr[i];
                arr[idx] = temp;
                answer_asc++;
            }
        }
 
        // 내림차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(reversed_arr[i] != arr_desc[i]){
                idx = idxMap_desc.get(reversed_arr[i]);
                idxMap_desc.put(arr_desc[i],idx);
                temp = arr_desc[i];
                arr_desc[i] = reversed_arr[i];
                arr_desc[idx] = temp;
                answer_desc++;
            }
        }
        
        // 더 작은값을 반환한다.
        return answer_asc > answer_desc ? answer_desc : answer_asc;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        int[] arr = new int[n];
 
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }
 
        int result = lilysHomework(arr);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

오랜만에 재미난 알고리즘 문제를 풀게되어 포스팅하게 되었습니다.

문제의 출처는 HackerRank 이며 아래의 주소입니다.


https://www.hackerrank.com/challenges/magic-square-forming/problem


문제설명에 대한 전문은 위의 링크에서 확인하실 수 있으며, 제 github에서도 확인하실 수 있습니다.

https://github.com/doorBW/hacker_rank_algorithm_practice


문제에 대해서 간단히 설명드리면 아래와 같습니다.


- Forming a Magic Square


먼저, Magic Square는 마방진이라고 이야기하겠고, 마방진에 대한 규칙은 다음과 같습니다.

3*3 형태를 가지는 마방진 행렬에서는 1부터 9까지 9개의 숫자를 이용하며, 모든 열과 행, 대각선의 합이 같아야합니다.


그럼 문제에 대해서 알아봅니다. 문제에서 input 값으로 3*3 행렬이 들어옵니다.

근데 이때 들어오는 행렬은 마방진의 규칙을 만족할 수도 만족하지 않을 수도 있습니다. 이러한 행렬을 마방진의 규칙에 만족시키기 위해서는 특정 숫자의 값을 바꿔야 하겠죠? 

즉, 아래와 같은 행렬이 input으로 들어온다고 생각해봅시다.


4 9 2

3 5 7

8 1 5


위의 행렬은 5가 두번쓰였을 뿐아니라, 세번째 열, 세번째 행, 왼쪽위에서 시작하는 대각선의 합이 14입니다.

이때 오른쪽 아래의 숫자 5를 6으로 바꿔주면 마방진의 규칙을 만족하게 됩니다.

이렇게 우리가 한 행동은 5 -> 6 으로 바꿔주는 것인데, 이때 1만큼의 변경을 cost 1로 계산합니다.

예를 들어 우리가 마방진을 만들기 위해 특정 위치에 있는 숫자들에 대하여 다음과 같은 변화를 주었다면,


2 -> 3, 7 -> 4


이때는 cost가 총 4가 되는 것입니다.

하지만 마방진은 단 하나만 존재하는 것이 아닐 것입니다.

이렇게 입력으로 주어진 행렬을 마방진으로 만들때 발생하는 최소 cost를 구하는 것이 문제입니다.



- Solving


먼저 전체적인 코드는 하단에 작성해두었습니다.

코드에서 주석을 통해 간단하게 나마 설명을 써두었지만, 조금 더 자세히 이야기해보려고 합니다.


처음 문제를 접근했을때, 문제를 어떻게 해결할 것인가 생각해보았습니다.

주어진 행렬에 대해서 특정 위치의 값을 변화시키며 그 행렬이 마방진의 규칙을 만족하게끔 하는 방법이 떠올랐으나, 이는 경우의 수가 너무 많았습니다.

그리고 어떤 위치의 숫자를 변화시켜야 할지 기준을 잡는 것도 너무 어렵다고 느껴졌습니다.


그리고 생각했던 방법은, 마방진 규칙을 만족하는 모든 행렬을 찾아내고, 입력받은 행렬과 하나씩 비교해가며 그 중 최소의 cost를 찾아내는 방법이었습니다.

물론 이 방법에서는 과연 마방진 규칙을 만족하는 모든 행렬이 몇개나 될까가 미지수였지만 그래도 처음에 생각했던 방법보다는 경우의 수가 훨씬 적을 것 같아서 해당 방법으로 풀이를 시작했습니다.


그리고 문제에서 주어진 것보다 더 많은 내용을 참고하기 위해 magic square, 마방진이라는 개념에 대해서 찾아보았습니다. 자세히 검색해본 것은 아니지만 대체로 마방진을 만드는 몇가지 원리에 대해서 이야기를 많이 하고 계셨습니다.

하지만 우리에게 실질적으로 필요했던건, 마방진의 원리 그 자체를 알아서 3*3에서 존재할 수 있는 모든 마방진이 필요했습니다.


따라서 직접 그 원리를 얕게나마 확인해보는 과정이 필요했습니다.


기본적으로 3*3 마방진에서 하나의 행 또는 열 또는 대각선의 합은 무조건 15입니다.(이를 증명하는 것은 쉬우니 스스로 해보시길 바랍니다.)

따라서 저는 먼저 1~9까지의 숫자들중 중복이 없는 3개의 숫자의 합이 15를 이루는 그룹을 만들었습니다. 예를 들면 3,5,7 과 같은 그룹입니다.

각 숫자의 순서와 상관없이 만들어 보았을때 이러한 그룹은 총 8개가 만들어졌습니다.


그리고 아래와 같은 형태의 행렬을 생각해보았습니다.


a  b  c

d  e  f

g  h  i


위의 행렬을 통해 8개의 식을 세울 수 있습니다.


a + b + c = 15

d + e + f = 15

g + h + i = 15

a + d + g = 15

b + e + h = 15

c + f + i = 15

a + e + i = 15

c + e + g = 15


그런데 이렇게 식을 세워보니 새로운 사실을 알 수 있었습니다.

위의 식에서 각 알파벳이 사용되는 횟수가 달랐습니다.

예를 들어 한가운데 존재하는 e 같은 경우 혼자서만 4번 사용되었고, 4개의 알파벳은 3번, 4개의 알파벳은 2번 사용되었습니다.

그리고 위의 식들은 숫자 위치만 적절히 조정하면 우리가 위에서 만든, 합이 15인 8개의 그룹입니다.


이러한 사실들을 통해 저는 위에서 만들었던 8개의 그룹을 바탕으로 각 숫자가 몇번 사용되었는지 카운팅 해본결과, 4번 사용되는 것은 숫자 5, 3번 사용되는 것은 2,4,6,8 이고 2번 사용되는 것은 1,3,7,9 이었습니다.

즉, 위에서 만든 알파벳 행렬이 마방진 규칙을 만족한다고 가정한다면 사실상 알파벳 e는 무조건 5의 값을 가질 것이며, 3번 사용되는 a,c,g,i는 2,4,6,8과 대응되고 나머지 알파벳은 1,3,7,9와 대응될 것입니다.


그렇다면, 우리가 만든 8개의 그룹을 한번 더 나누어 볼 수 있습니다.

숫자 5가 포함된 것은 무조건 2행에서만 사용될 수 있기 때문입니다.

따라서 저는 첫번째 행과 세번째 행에 사용될 수 있는 그룹과, 두번째 행에 사용될 수 있는 그룹을 만들었습니다.

추후 실제로 이 그룹들을 바탕으로 마방진 규칙을 만족하는 행렬을 만들 것이기에 이번에는 숫자들의 순서(위치)등을 고려하여 모든 경우의 수를 다루었습니다.

그리고 아래의 추가적인 조건을 활용하였습니다.


- 숫자 5가 포함된 그룹에서 나머지 두 숫자는 모두 1,3,7,9 중의 숫자이다.(2번 사용되는 숫자들)


이를 통해 second_lines 와 other_lines 라는 두개의 그룹을 만들었으며, 이제 이러한 두 그룹을 이용해서 행렬을 만들었습니다.

그리고 행렬을 만들면서 마방진의 규칙을 추가하여 최종적으로 마방진 규칙을 만족하는 행렬은 magic_square 이라는 리스트에 추가하였습니다.


이러한 과정을 통해 마방진 규칙을 만족하는 모든 행렬은 총 8개가 되었습니다.

걱정했던 것과는 달리 적은 개수이기에 최종적으로 cost를 구하기 위한 과정을 가졌습니다.

입력받은 행렬을 8개의 행렬에 대해 각 위치별 숫자의 차이값을 구해서 최소의 cost를 구하여 반환하였습니다.


위의 과정을 통해 작성한 코드는 HackerRank에서 100% 통과를 받았습니다.


전체 코드는 아래와 같습니다.


Forming a Magic Square Code(Click)


코드가 완성도 있거나, 완벽하다고는 생각하지 않습니다.

코드에 대한 피드백은 언제든지 환영이며, 추가적으로 궁금하신 점은 댓글이나 이메일을 이용해주시면 감사하겠습니다.

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc