[프로그래머스] 2018 KAKAO BLIND RECRUITMENT - 비밀지도

문제 설명

비밀지도

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

매개변수	값
n	5
arr1	[9, 20, 28, 18, 11]
arr2	[30, 1, 21, 17, 28]
출력	["#####","# # #", "### #", "# ##", "#####"]

매개변수	값
n	6
arr1	[46, 33, 33 ,22, 31, 50]
arr2	[27 ,56, 19, 14, 14, 10]
출력	["######", "### #", "## ##", " #### ", " #####", "### # "]

 

 

 

풀이

 

10진수를 2진수로 만드는게 핵심이었습니다.

 

풀고나서 다른 분들의 풀이를 참고하니 저에비해 코드량이 매우 짧았습니다.

 

예를들어서 10진수 9를 2진수로 바꾸려면

xxxxxxxxxx
int a = 9;      
System.out.println(Integer.toBinaryString(a));
// 결과 : 1001

 

이렇게 간단하게 할 수 있었습니다.

 

저는 Integer.toBinaryString 메소드의 존재를 몰랐기 때문에 비효율적으로 10진수에서 2진수를 구하는 과정을 거쳤습니다.

 

제가 했던 방법은 스택을 이용하여 숫자를 계속 2로 나눠주면서 나머지를 스택에 넣어줬습니다.

 

그리고 이렇게 구한 2진수값을 바탕으로 2개의 지도에 하나하나 넣어주고

주어진 조건에 따라 계산을 해서 코드량이 길었습니다.

 

일단 제가 푼 코드를 먼저 첨부하겠습니다.

get메소드는 2진수를 구하기 위한 함수입니다.

 

get메소드에서 cnt라는 변수가 있는데, 이는 자리수를 맞추기 위함입니다.

이게 무슨말이냐면 9를 2진수로 변환하면 1001 이 나오는데

n = 5라면 01001 이 되야 하니 앞에 0을 더 붙여주기 위한 변수였습니다.

 

import java.util.*;
class Solution {
    public static String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        String map1[][] = new String[n][n];
        String map2[][] = new String[n][n];
        
        
        get(n,arr1,map1);
        get(n,arr2,map2);
        
        
        for(int i=0; i<n; i++) {
            String str="";
            for(int j=0; j<n; j++) {
                if(map1[i][j].equals("#")) {
                    str+="#";
                }
                else if(map2[i][j].equals("#")) {
                    str+="#";
                }
                
                if(map1[i][j].equals(" ") && map2[i][j].equals(" ")) {
                    str+=" ";
                }
            }
            answer[i] = str;
        }
        
        return answer;
    }
    public static void get(int n, int arr[],String map1[][]) {
        Stack<Integer>stack = new Stack<>();
        for(int i=0; i<n; i++) {
            int cnt = 0;
            int num = arr[i];
​
            while(num!=1 && num!=0) {
                cnt++;
                stack.push(num%2);
                num/=2;
            }
            
            if(num==1) {
                cnt++;
                stack.push(1);
            }
            
            if(cnt != n) {
                int s_num = Math.abs(cnt-n);
                for(int j=0; j<s_num; j++) {
                    stack.add(0);
                }
            }
​
            int j =0;
            while(!stack.isEmpty()) {
                int pop_num = stack.pop();
                if(pop_num==1) {
                    map1[i][j] = "#";
                    j++;
                }
                else {
                    map1[i][j] =" ";
                    j++;
                }
            }
        }
    }
}

 

 

다 풀고나서 다른분들의 코드를 참고해서 푼 풀이는 아래와 같습니다.

 

import java.util.*;
class Solution {
    public static String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        
        for(int i=0; i<n; i++) {
            String binary = Integer.toBinaryString(arr1[i]|arr2[i]);
            binary = String.format("%"+n+"s", binary);
            binary = binary.replaceAll("1", "#");
            binary = binary.replaceAll("0", " ");
            answer[i] = binary;
        }
        
        return answer;
    }
}

 

카카오는 문자열 처리에 대해서 자주 나온다고 했는데, 위의 코드에서 사용된 메소드를 정리해보겠습니다.

 

String.format에 대해서 알아보면

String.format("%5s",바꿀 문자열변수);

(여기서 5는 맞추길 원하는 자리수입니다.)

 

이를 표현하면

String.format(%자리수s , 바꿀문자열 변수);

이런식으로 돼 있습니다.

 

아까의 예시를 들어봅시다.

String a = Integer.toBinaryString(9); 를 하면

1001이 나옵니다

여기서 String.format("%5s",a); 를 해주면

(공백)1001 이렇게 나오게 됩니다.

 

기존에는 4자리였는데 제일 앞에 공백이 생겨 총 5자리 문자열이 완성 됐습니다.

 

01001 이나 (공백)1001 이나 위 문제를 처리하는데는 지장이 없습니다.

애초에 0으로 표시된 부분을 공백으로 바꾸고 1로 표시된 부분을 "#" 으로 바꿔줘야하는데

미리 돼 있으니 굳이 할 필요가 없는 것이죠

 

arr[1]|arr[2]는 비트연산으로

arr[1] = 1000

arr[2] = 1001

 

일 경우 or연산을 통해 1001이 됩니다.

 

문제의 조건에서 2개의 맵 중 하나만 벽이 있어도 원본 지도에는 벽이고 2개의 지도 모두 0 인경우는

공백으로 설정한다 했으니 비트연산으로 해결 할 수 있는 문제였습니다.