[프로그래머스/Lv.1] 비밀지도(2018 KAKAO BLIND RECRUITMENT) - Java

📌 문제

프로그래머스

 

카카오 신입 공채 1차 코딩 테스트 해설은 다음과 같다.

📌 첫 번째 풀이

해설에서는 비트 연산을 묻는 문제라고 나와있지만..처음 풀 때 비트 연산은 전혀 생각하지 못했다. 나중에 비슷한 문제가 나온다면 비트 연산을 떠올릴 수 있겠지..🥲 이 풀이는 비트 연산으로 푼 것이 아니니 두 번째 풀이부터 봐도 괜찮다. 시행착오를 기록하려고 적어본다. 

 

우선 처음에는 0부터 n까지 for문을 돌리며 무작정 arr1과 arr2를 이진수로 변환하였다. Integer.toBinaryString()을 이용하면 10진수 숫자를 2진수 String으로 바꿀 수 있다.

String binary1 = Integer.toBinaryString(arr1[i]);
String binary2 = Integer.toBinaryString(arr2[i]);

 

그런데 예를 들어 2진수로 변환된 값이 1011일 경우, 앞에 0이 생략되었다. 나중에 같은 인덱스의 숫자를 비교하고 싶었는데, 이렇게 되면 자릿수가 맞지 않아 오류가 발생할 것이라고 생각했다. 그런데 앞에 0을 붙이는 과정에서 상당히 헤매다가..이 부분은 검색을 했다. 문자열 "0"을 (n - 문자열 길이) 만큼 반복하고 그 뒤에 기존에 이진수로 변환했던 문자열을 붙여주는 것이다. 이렇게 하면 앞에 채워지지 못한 0이 모두 채워져 자릿수가 맞게 된다.

binary1 = "0".repeat(n - binary1.length()) + binary1;
binary2 = "0".repeat(n - binary2.length()) + binary2;

 

그리고나서 해당 문자열을 String 배열로 바꾼다.

String[] biArr1 = binary1.split("");
String[] biArr2 = binary2.split("");

 

또다시 0부터 n만큼 for문을 돌면서 각 String 배열의 j번째 글자가 하나라도 1이라면 벽이므로 '#'를 추가하고, 모두 0이라면 공백을 추가한다. 이때는 문자열 연산이 많이 일어나므로 StringBuilder를 사용한다.

StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
    if (biArr1[j].equals("1") || biArr2[j].equals("1")) {
       sb.append("#");
    } else {
       sb.append(" ");
    }
    answer[i] = sb.toString();
}

 

이렇게 푼 코드는 정답이긴 했지만, 다른 사람들의 코드를 보고 이렇게 어렵고 길게 풀 필요는 없다는 걸 깨달았다..

📌 두 번째 풀이

비트연산으로 푼 코드는 다음과 같다. for문으로 0부터 n까지 돌면서 Integer.toBinaryString()으로 10진수를 2진수 String으로 바꾸는데, 이 때 OR 비트 연산을 동시에 할 수 있었다..! 모두 변환 후 "0"을 채워주는 건 똑같았다. 하지만 for문을 또 돌리며 문자열 연산을 하지 않고 replaceAll()을 이용해 "1"은 "#"으로, "0"은 공백으로 바꿔준 후 배열에 넣었다. 어차피 위에서 OR 연산을 했기 때문에 일일히 비교하지 않아도 되는 것이다.

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

📌 비트 연산

• AND 연산( & ) : 둘 다 1일 경우 1로 변환
• OR 연산( | ) : 둘 중 하나만 1이어도 1로 변환
• XOR 연산( ^ ) : 두 수가 다른 경우 1로 변환
• NOT 연산( ~ ) : 각 자리수를 반대로 변환
• SHIFT 연산( <<, >>, >>> )
  • << : 이진수의 각 자리를 왼쪽으로 n칸 밀고 첫째 자리와 뒤에 공간은 0으로 채움
  • >> : 이진수의 각 자리를 오른쪽으로 n칸 밀고 밀면서 사라지는 자리수는 삭제함, 맨 앞은 동일한 부호 비트로 채움
  • >>> : 오른쪽 SHIFT 연산 시 항상 양수만 고려함(오른쪽으로 밀고 남은 공간 항상 0으로 채)

📌 전체 코드

처음 작성한 코드

import java.util.*;

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for (int i = 0; i < n; i++) {
            String binary1 = Integer.toBinaryString(arr1[i]);
            String binary2 = Integer.toBinaryString(arr2[i]);
            binary1 = "0".repeat(n - binary1.length()) + binary1;
            binary2 = "0".repeat(n - binary2.length()) + binary2;
            String[] biArr1 = binary1.split("");
            String[] biArr2 = binary2.split("");
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (biArr1[j].equals("1") || biArr2[j].equals("1")) {
                    sb.append("#");
                } else {
                    sb.append(" ");
                }
                answer[i] = sb.toString();
            }
        }
        
        return answer;
    }
}

 

 

비트 연산을 이용한 코드

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