[Programmers] Lv1_[1차] 비밀지도

💻JAVA 코드 바로보기

 

 

□문제 설명

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

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]
출력	["######", "### #", "## ##", " #### ", " #####", "### # "]

 

 

---

🌼JAVA 알고리즘

 

□초기화면

 

 

 

 

 

□풀이과정

1) 매개변수로 주어진 배열 요소를 차례대로 2진수로 변환하여 새로운 배열에 저장한다. arr1의 결과배열과 arr2의 결과배열을 비교하여 둘중 하나라도 벽이면 벽으로 출력배열(answer)에 표시한다. 1)의 풀이로 풀다가, 아래와 같이 새로운 배열과 변수가 너무 많이 필요해서 비트연산자 풀이로 바꿔보았다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        int[] arr1_C = new int[n*n];
        int[] arr2_C = new int[n*n];
        int index_1 = n*n-1;
        int index_2 = n*n-1;
        
        for(int i=0;i<arr1.length;i++){
            for(int j=n-1;j>=0;j--){
                arr1_C[index_1--] = arr1[i]%2;
                arr1[i]/=2;
            }
        }
        for(int i=0;i<arr2.length;i++){
            for(int j=n-1;j>=0;j--){
                arr2_C[index_2--] = arr2[i]%2;
                arr2[i]/=2; 
            }
        }

        
        return answer;
    }
}

우선 arr1과 arr2를 비트연산자 '|'를 사용하여 나온 결과값만 출력해보았다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        String str = "";
        
        for(int i=0;i<n;i++){
            System.out.println(Integer.toBinaryString(arr1[i] | arr2[i]));
        }
        
        
        return answer;
    }
}

정상 결과

비정상 결과

테스트2의 결과를 보면, 4행과 5행의 열 개수가 다른 행과 같지 않았다. 이 문제는 조건 "x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다." 에서 알 수 있듯이, 이진수가 6자리가 나오지 않았다는 의미이므로 각 행의 길이가 n과 같지 않을 때에 뒷자리에 0을 추가해주는 방식을 사용해보았다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i=0;i<n;i++){
            answer[i] = (Integer.toBinaryString(arr1[i] | arr2[i]));
            if(answer[i].length()!=n) answer[i]+="0";
        }
        for(int i=0;i<n;i++){
            System.out.println(answer[i]);
        }
        
        return answer;
    }
}

테스트1과 테스트2의 출력결과는 기댓값과 같으므로, 이제 1과 0을 #과 공백으로 바꾸도록 replace()메소드를 사용했다. replace메소드는 String타입에서 첫번째 매개변수에 해당하는 값을 두번째 매개변수로 바꾸어주는 역할을 한다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i=0;i<n;i++){
            answer[i] = (Integer.toBinaryString(arr1[i] | arr2[i]));
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                answer[i] = answer[i].replace("1","#");
                answer[i] = answer[i].replace("0"," ");
            }
        }
        
        return answer;
    }
}

하지만 제출 코드에서 원하는 결과가 나오지 않았는데, 결과값은 "#### ", 기댓값은 " #### " 인 것으로 보아 각 행의 길이가 n과 같지 않을 때 공백이 필요한 자리는 뒤가 아닌 가장 앞임을 알 수 있다. 또, n과 같지 않다는 한 자리가 부족하다는 뜻이 아니기 때문에, 부족할 때마다 앞에 공백을 추가해주는 코드로 수정하였다.

 

 

 

 

 

 

□완성코드

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        int count = 0;
        for(int i=0;i<n;i++){
            count = 0;
            answer[i] = (Integer.toBinaryString(arr1[i] | arr2[i]));
            if(answer[i].length()!=n) count = n-answer[i].length();
            for(int j=0;j<count;j++)  answer[i]="0"+answer[i];
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                answer[i] = answer[i].replace("1","#");
                answer[i] = answer[i].replace("0"," ");
            }
        }

        return answer;
    }
}

 

 

 

 

 

---

□링크

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

 

About Me