[Java][programers][level1] 비밀지도 (최적화의 중요성)

package study.algorithms.programers.level1.비밀지도;

import java.util.Arrays;

public class Solution {
//내코드
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        Arrays.fill(answer, "");
        String format = "%0"+Integer.toString(n)+"d";
        for (int i = 0; i < n; i++) {
            String binaryString1 = String.format(format,Long.parseLong(Long.toBinaryString(arr1[i])));
            String binaryString2 = String.format(format,Long.parseLong(Long.toBinaryString(arr2[i])));

            for (int j = 0; j < n; j++) {
                char binaryString1Index = binaryString1.charAt(j);
                char binaryString2Index = binaryString2.charAt(j);
                char tmp = binaryString1Index == '1' ? '#' : binaryString2Index == '1' ? '#' : ' ';
                answer[i] += tmp;
            }

        }
        return answer;
    }
    
    //좋은 코드
    public String makeSharp(int n, int m) {
        if(n == 0) {
            if( m > 0) {
                String str = "";
                for(int i = 0; i < m; i++) {
                    str += " ";
                }
                return str;
            }
            else return "";
        }
        else {
            return n % 2 == 0 ? makeSharp(n/2, m-1) + " " : makeSharp(n/2, m-1) + "#";
        }
    }
    public String[] solution2(int n, int [] arr1, int [] arr2) {
        String [] answer = new String[n];
        int [] secretMap = new int[n];
        for(int i = 0; i < n; i++) {
            secretMap[i] = arr1[i] | arr2[i];
            answer[i] = makeSharp(secretMap[i], n);
        }
        return answer;
    }
}
//                int binary1 = Integer.parseInt(String.valueOf(binaryArr1.charAt(j)));
//                int binary2 = Integer.parseInt(String.valueOf(binaryArr2.charAt(j)));
//                int tmp = binary1 == 1 ? 1 : binary2 == 1 ? 1 : 0;

내 코드는 보기는 살짝 좋을지 몰라도 성능이 너무 떨어진다.

잘못된점

 

✔ 굳이 arr1[i]를 toBinaryString으로 String으로 변환하고 0이 빌 경우를 대비해서 String.format을 사용하여 %0을 채울 필요가 없었다.

그냥 바로 | 비트연산자사용하면 됬다.

String format = "%0"+Integer.toString(n)+"d";
for (int i = 0; i < n; i++) {
    String binaryString1 = String.format(format,Long.parseLong(Long.toBinaryString(arr1[i])));
    String binaryString2 = String.format(format,Long.parseLong(Long.toBinaryString(arr2[i])));

    for (int j = 0; j < n; j++) {
        char binaryString1Index = binaryString1.charAt(j);
        char binaryString2Index = binaryString2.charAt(j);
        char tmp = binaryString1Index == '1' ? '#' : binaryString2Index == '1' ? '#' : ' ';
        answer[i] += tmp;
    }

}

따라서 더 코드를 줄여 봤다.

    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        Arrays.fill(answer, "");
        String format = "%0"+Integer.toString(n)+"d";
        for (int i = 0; i < n; i++) {
//            String binaryString1 = String.format(format,Integer.parseInt(Integer.toBinaryString(65535)));
            //65535를 이진수로 변환하면 1111111111111111의 문자로 되는데 이 문자를 다시 Int로(parseInt) 바꾸려하면 int범위를 벗어난다.

            String binaryString1 = String.format(format,Long.parseLong(Integer.toBinaryString(arr1[i])));
            String binaryString2 = String.format(format,Long.parseLong(Integer.toBinaryString(arr2[i])));

            for (int j = 0; j < n; j++) {
                char binaryString1Index = binaryString1.charAt(j);
                char binaryString2Index = binaryString2.charAt(j);
                char tmp = binaryString1Index == '1' ? '#' : binaryString2Index == '1' ? '#' : ' ';
                answer[i] += tmp;
            }

        }
        return answer;
    }

↓

public String[] solution3(int n, int [] arr1, int [] arr2) {
    String [] answer = new String[n];
    int [] arrIndex = new int[n];
    String format = "%0"+Integer.toString(n)+"d";
    for(int i = 0; i < n; i++) {
        arrIndex[i] = arr1[i] | arr2[i];
        answer[i] = (String.format(format,Long.parseLong(Integer.toBinaryString(arrIndex[i])))).replaceAll("1", "#").replaceAll("0", " ");
    }
    return answer;
}

 

코드는 짧아졌으나 가장 큰 문제는 성능이 안 나온다는 것이다.

밑의 코드에 비해 성능이 10배 이상 안나온다.

//좋은 코드
    public String makeSharp(int n, int m) {
        if(n == 0) {
            if( m > 0) {
                String str = "";
                for(int i = 0; i < m; i++) {
                    str += " ";
                }
                return str;
            }
            else return "";
        }
        else {
            return n % 2 == 0 ? makeSharp(n/2, m-1) + " " : makeSharp(n/2, m-1) + "#";
        }
    }
    public String[] solution2(int n, int [] arr1, int [] arr2) {
        String [] answer = new String[n];
        int [] secretMap = new int[n];
        for(int i = 0; i < n; i++) {
            secretMap[i] = arr1[i] | arr2[i];
            answer[i] = makeSharp(secretMap[i], n);
        }
        return answer;
    }

성능이 낮은데에는 여러가지 이유가 있는 것 같다.

✔ Integer.toBinaryString, Long.parseLong, String.format과 같은 무언가를 변환해주는 메소드들이 성능을 다 깎아 먹었다.

 

✔ 성능을 위한다면 무언가를 변환하는 메소드는 사용하지 말아야한다.