비밀 지도_Java

2018 KAKAO BLIND RECRUITMENT

🔥 비밀 지도 🔥

---

👀 문제

네오가 프로도가 평소 비상금을 숨겨둔 장소를 알려줄 비밀지도를 손에 넣었다. 하지만 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다.

해독하는 방법은 아래와 같다.

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

네오가 프로도의 비상금을 손에 넣을 수 있도록 암호를 해독하는 solution을 완성해보자.

---

👩‍💻 입력 & 🧙 출력

입력 형식

입력으로 지도의 한 변 크기 n과 2개의 정수배열 arr1, arr2가 주어진다.
- 1 ≦ n ≦ 16
- arr1, arr2는 길이 n인 정수배열로 주어짐
- 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n이하이다.
즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

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

---

🙋‍♀️ 풀이

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[][] map = new String[n][n];
        String[] answer = new String[n];
         
         1️⃣
        for(int i=0;i<arr1.length;i++){
 			
            2️⃣
            String dots1 = String.format("%0"+n+"d",Long.parseLong(Integer.toBinaryString(arr1[i])));
            char[] dot1 = dots1.toCharArray();
            
            String dots2 = String.format("%0"+n+"d",Long.parseLong(Integer.toBinaryString(arr2[i])));
            char[] dot2 = dots2.toCharArray();
            
            3️⃣
            for(int j=0;j<dot1.length;j++){
                if(dot1[j] =='0' && dot2[j] =='0'){
                    map[i][j] = " ";   
                }else if(dot1[j] == '1' || dot2[j] == '1'){
                    map[i][j] = "#";
                }
                
            }
        }
        
        4️⃣
        for(int i=0;i<map.length;i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<map[i].length;j++){
                sb.append(map[i][j]);
            }
             answer[i] = sb.toString();
        }
        return answer;
    }
}

이차원 배열 map은 두개의 지도를 합한 최종 지도의 모습을 담는 배열

1️⃣ arr1과 arr2의 길이는 같으므로 arr1의 길이만큼 반복문을 돌린다.

2️⃣ arr1과 arr2의 요소를 이진수로 바꾸고 char형의 배열에 대입한다.
	
    * 이진수로 바꾸기 * 
    - Integer.toBinaryString : 2진수로 바꿈
    - Long.parseLong : long자료형으로 변환
    - String.format("%0"+n+"d", ...) : ...의 형식을 n자리수 정수로 설정하고 빈공간은 0으로 채움
      String.format을 설정하지 않으면 빈공간이 출력되지 않기 때문에 꼭 해주어야함
      
    * char형 배열에 대입하기
    - toCharArray : String형의 dots1과 dots2를 배열로 저장
      
      
3️⃣ dot1의 길이만큼 반복하면서  dot1과 dot2의 값이 0이라면 해당 위치에는 빈값을 dot1의 값이 1이거나 dot2의 값이 1이라면 해당 위치에는 #를 대입한다.

4️⃣ map의 길이만큼 반복하면서 StringBuilder를 이용해서 각 요소를 append해주고 answer에 대입한다.

---

💬 다른 풀이

1. 비트연산자와 substring

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = new String[n];
      String temp;

      for(int i = 0 ; i < n ; i++){
      	  1️⃣
          temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
          2️⃣
          temp = temp.substring(temp.length() - n);
          3️⃣
          temp = temp.replaceAll("1", "#");
          4️⃣
          temp = temp.replaceAll("0", " ");
          5️⃣
          answer[i] = temp;
      }

      return answer;
  }
}

1️⃣ n만큼 반복하면서 비트연산자를 이용해서 arr1과 arr2의 i번째를 비교한 후 Integer.toBinaryString을 이용해서 이진수로 바꾼다. String.format을 이용해서 16자리 String으로 변환한다.

여기서의 temp는 테스트 1을 예로들어보자면 아래와 같다.
           11111
           10101
           11101
           10011
           11111


2️⃣ substring을 이용해서 temp의 길이 즉 16에서 n만큼값만큼 문자열을 제거해준다.

3️⃣ replaceAll을 이용해서 1인 부분은 "#"으로
4️⃣ 0인 부분은 " " 으로 변환한다.
5️⃣ answer의 i번째에 temp를 대입해준다.

---

👏 마무리

카카오문제를 스스로 풀어서 좋았는데...

실행시간 차이가 심하게 많이 나는걸 보고는 내코드가 💩인걸 깨달았다. 그리고 비트연산자를 사용할 생각을 했었다면 버거롭게 하나하나 비교하고 다시 담는 과정은 하지 않았을것이다.

왜 나아지질 않는걸까