Programmers School level 1: [1차] 비밀지도

<풀기 전 생각>

비밀지도의 정보가 이진 정보로 저장되어 있기 때문에 bit 연산자를 활용하거나 자바의 Integer.bitCount 혹은 Intger.highestOneBit() 같은 메소드를 활용해야 한다는 생각을 하고

문자열을 만들어야 하므로 StringBuilder를 써야 한다는 판단을 하고 문제 풀이에 들어갔다.

 

<중간 문제점>

각각의 bit의 정보가 1 인지 0인지 어떻게 판별해야 되나 고민이 되었는데 ex(1101) 

1000 0100 0010 0001 같은 mask를 만들고 & (and) 연산자를 활용하면 되지 않을까? 했는데 바로 통과 할 수 있었다. 

 

<최종 코드>

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n)
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        StringBuilder mapMaker = new StringBuilder("");
        // 벽의 정보는 이진법으로 저장되어 있음
        // or 연산을 통해 1개라도 벽이라면 벽으로 처리
        for(int i=0;i<n;i++)
            arr1[i] |= arr2[i];

        for(int j=0;j<n;j++){
            int target = arr1[j];
            // 제일 높은 지수의 자리 부터 판별
            for(int i=n-1;i>=0;i--){
                int mask = (int)Math.pow(2,i);
                if((target&mask)==0)
                    mapMaker.append(" ");
                else
                    mapMaker.append("#");
            }
            answer[j] = mapMaker.toString();
            mapMaker.delete(0,mapMaker.length());
        }

        return answer;
    }
}

<메모>

 

우수 풀이의 코드를 본 결과 다음과 같음 함수를 활용하여 시간 복잡도를 O(n) 공간 복잡도를 O(1)로 획기적으로 줄인 코드를 볼 수 있었는데 이진 정보를 바탕으로 문자열을 만들어야 할 때 사용하면 좋을 것 같다. 

result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
//-------------------------------------------------------------------------
temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
temp = temp.substring(temp.length() - n);
temp = temp.replaceAll("1", "#");
temp = temp.replaceAll("0", " ");