비밀지도

안녕하세요, 오늘은 정말 오랜만에 코딩 테스트 연습 문제를 풀이하려고 합니다.
이번 문제는 2018 카카오 블라인드 채용에서 출시되었으며 꽤 난이도가 있는 문제입니다.

📚 문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다.

그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다.

그러나 다행히도 네오는 지도 암호를 해독할 방법을 적어놓은 메모도 운 좋게 함께 발견했다.

 

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백("") 또는 벽("#") 두 종류로 이루어져 있다.

2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 지도1 또는 지도2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다.

3. 지도1 또는 지도2에서 모두 공백인 부분은 전체 지도에서도 공백이며 지도1과 지도2는 각각 정수 배열로 암호화되어 있다.

4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0이라고 할 때 얻어지는 이진수에 해당하는 값의 배열이다.

 

네오가 프로도의 비상금을 손에 넣을 수 있도록

비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성해라.

코딩테스트 연습 - [1차] 비밀지도

🗣 입출력 예시

n	arr1	arr2	출력
5	[9, 20, 28, 18, 11]	[30, 1, 21, 17, 28]	["#####", "# # #", "### #", "#  ##", "#####"]
6	[46, 33, 33, 22, 31, 50]	[27, 56, 19, 14, 14, 10]	["######", "###  #", "##  ##", " #### ", " #####", "### # "]

첫 번째 예시에서 매개변수로 전달받은 n의 값이 5이기에 문제에서의 비밀지도는 한 변의 길이가 5인 정사각형이 됩니다. 또한 지도1과 지도2에 해당하는 정수 배열 arr1 및 arr2를 매개변수로 전달받으며 각각의 암호화된 배열을 비밀지도에 맞게 해석해야 합니다.

 

암호화된 배열을 해석하기 위해 배열 속 각 인덱스에 해당하는 값을 이진수로 변환하며 이 변환된 값이 바로 비밀지도에서의 가로줄에 해당하게 됩니다. 그 후 arr1 지도1과 arr2 지도2를 서로 조건에 맞게 비교하면서 최종적인 비밀지도를 완성하는 것입니다.

 

	암호화 배열 (정수)	해독화 배열 (이진수)
arr1	[9, 20, 28, 18, 11]	[01001, 10100, 11100, 10010, 01011]
arr2	[46, 33, 33, 22, 31, 50]	[11110, 00001, 10101, 10001, 11100]

위와 같은 방식의 로직으로 문제를 풀이할 시 가장 중요한 점은 암호화된 배열을 해석하기 위해 배열 속 간 인덱스에 해당하는 값을 이진수로 변환할 때 그 변환된 이진수의 길이가 n과 같도록 구성돼야 한다는 것이 이번 문제에서 가장 중요하다고 생각하고 있습니다.

 

두 번째 예시 또한 첫 번째 예시 때 설명했던 방식을 활용해 동일하게 문제를 풀이할 수 있기 때문에 상세한 설명은 생략하도록 하겠습니다. 아래의 표와 사진을 통해 스스로 두 번째 예시에 대한 로직을 천천히 다시 한번 생각해보고 해결해보시는 것을 추천합니다.

 

	암호화 배열 (정수)	해독화 배열 (이진수)
arr1	[46, 33, 33, 22, 31, 50]	[101110, 100001, 100001, 010110, 011111, 110010]
arr2	[27, 56, 19, 14, 14, 10]	[011011, 111000, 010011, 001110, 001110, 001010]

📨 나의 해결책 (1시간 30분 소요)

# solution 메소드

solution 메소드는 입출력 예시 때 언급되었던 각각의 요소들을 매개변수로 전달받으며 이 데이터들을 활용하여 각각의 기능을 구현하는 함수들의 매개변수 인자로 전달하는 역할을 하고 있습니다. 또한 프로그램의 최종적인 결과를 리턴하는 함수이기도 합니다.

public String[] solution(int n, int[] arr1, int[] arr2) {
    String[] formatArr1 = formatBinaryString(n, arr1);
    String[] formatArr2 = formatBinaryString(n, arr2);

    String[] mixArr = mixData(n, formatArr1, formatArr2);
    return mixArr;
}

# formatBinaryString 메소드

formatBinaryString 메소드는 매개변수로 비밀지도의 한 변의 길이 n과 암호화된 지도 배열 arr을 전달 받고 있습니다. 이 메소드는 바로 위에서 살펴보았던 solution 메소드에서 호출하며 매개변수로 전달받은 암호화된 배열을 이진수로 해독하는 역할을 합니다.

 

이 과정 속에서 비밀지도의 한 변의 길이 n을 전달받는 이유는 앞에서도 설명했듯이 이진수의 길이가 n과 같도록 구성되도록 하기 위해서입니다. 이 부분은 formatBinaryString 메소드에서 가장 핵심이며 중요하다고 할 수 있는 부분이기에 주의하시기 바랍니다.

public String[] formatBinaryString(int n, int[] arr) {
    String[] formatArr = new String[n];

    for (int i = 0; i < n; i++) {
        formatArr[i] = String.format("%0"+n+"d", Long.parseLong(Integer.toBinaryString(arr[i])));
    }
    return formatArr;
}

# mixData 메소드

mixData 메소드는 매개변수로 비밀지도의 한 변의 길이 n과 해독화된 지도 배열 formatArr1, formatArr2를 전달받으면서 solution 함수에서 호출됩니다. 이 메소드에서는 해독화된 각 배열들의 인덱스에 해당하는 값들을 순차적으로 비교하는 과정을 거치면서 위에서 살펴본 조건에 맞게 실질적으로 비밀 지도를 최종적으로 조합하는 역할을 하는 아주 중요한 함수라고 말할 수 있습니다.

public String[] mixData(int n, String[] formatArr1, String[] formatArr2) {
    String[] mixArr = new String[n];

    for (int i = 0; i < n; i++) {
        mixArr[i] = "";
        for (int j = 0; j < n; j++) {
            if (formatArr1[i].charAt(j) != formatArr2[i].charAt(j)) {
                mixArr[i] += "#";
            } else if (formatArr1[i].charAt(j) == formatArr2[i].charAt(j)) {
                if (formatArr1[i].charAt(j) == '0') mixArr[i] += " ";
                else if (formatArr1[i].charAt(j) == '1') mixArr[i] += "#";
            }
        }
    }
    return mixArr;
}

[ 전체 소스코드 ]

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] formatArr1 = formatBinaryString(n, arr1);
        String[] formatArr2 = formatBinaryString(n, arr2);

        String[] mixArr = mixData(n, formatArr1, formatArr2);
        return mixArr;
    }

    public String[] formatBinaryString(int n, int[] arr) {
        String[] formatArr = new String[n];

        for (int i = 0; i < n; i++) {
            formatArr[i] = String.format("%0"+n+"d", Long.parseLong(Integer.toBinaryString(arr[i])));
        }
        return formatArr;
    }

    public String[] mixData(int n, String[] formatArr1, String[] formatArr2) {
        String[] mixArr = new String[n];

        for (int i = 0; i < n; i++) {
            mixArr[i] = "";
            for (int j = 0; j < n; j++) {
                if (formatArr1[i].charAt(j) != formatArr2[i].charAt(j)) {
                    mixArr[i] += "#";
                } else if (formatArr1[i].charAt(j) == formatArr2[i].charAt(j)) {
                    if (formatArr1[i].charAt(j) == '0') mixArr[i] += " ";
                    else if (formatArr1[i].charAt(j) == '1') mixArr[i] += "#";
                }
            }
        }
        return mixArr;
    }
}

🎨 모범 답안

모범답안은 아래와 같습니다. 코드의 내부 로직은 거의 비슷하지만 코드의 수는 제가 작성한 것보다 모범 답안의 코드가 훨씬 적습니다. 이것이 가능한 이유는 모범 답안의 코드에서는 암호화된 배열들을 해독하기 위해 OR 비트 연산자를 사용했기 때문입니다. 이 연산자를 사용하면서 암호화된 각 배열들을 비트 단위로 해독하였기에 제가 작성한 코드보다 훨씬 더 간단하게 구현이 가능했습니다.

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
        }

        for (int i = 0; i < n; i++) {
            result[i] = String.format("%" + n + "s", result[i]);
            result[i] = result[i].replaceAll("1", "#");
            result[i] = result[i].replaceAll("0", " ");
        }

        return result;
    }
}

👍 글을 마치며

오늘은 코딩 테스트 연습 문제 중 비밀지도라는 문제를 풀어보았습니다. 이번 문제를 풀면서 저는 자료구조의 중요성을 크게 느끼게 되었습니다. 수학 문제도 다양한 방식으로 문제를 풀 수 있듯이 코딩 테스트 문제 또한 마찬가지입니다. 그러나 다양한 방법들 중 가장 최적화되고 간단한 방법을 선택하여 문제를 풀 수 있도록 도와주는 것이 수학에서의 공식입니다. 이처럼 코딩 테스트 연습 문제 또한 특정 문제에 적합하며 문제를 쉽게 풀 수 있도록 도와주는 자료구조라는 것이 존재합니다. 이를 잘 활용하면 오늘 문제의 모범답안과 같이 효율적으로 코드를 짤 수 있을 것입니다. 여러분들도 평소에 자료구조에 대해서 열심히 공부하여 잘 활용하시기 바랍니다.