[2018 Kakao Blind Recruitment 1차] Q1. 비밀 지도(C++, Python, JAVA)

programmers.co.kr/learn/courses/30/lessons/17681

 

알고리즘 분류

Implementation, Bit operation

 

풀이

"지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽"이라는 문제의 조건은 비트 연산 OR을 통해 쉽게 얻을 수 있습니다. 비트 연산 대신 if, else를 이용해도 되긴 합니다만 구현이 더러워집니다.

 

정수로부터 # 혹은 공백으로 구성된 문자열 배열을 만들어내는 것은 2로 나눈 나머지를 취하고 2로 나누는 작업을 반복하거나, 비트 연산을 활용하거나, 파이썬의 bin 함수 혹은 자바의 toBinaryString 메소드를 활용하는 방법이 있습니다. 어떤 방법을 사용해도 크게 어렵지 않게 구현할 수 있습니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

string i2str1(int x, int n) {
    string ret(n, ' ');
    for(int i = 0; i < n; i++){
        if(x & (1 << i)) ret[n-1-i] = '#';
    }
    return ret;
}

string i2str2(int x, int n) {
    string ret(n, ' ');
    for(int i = 0; i < n; i++){
        if(x % 2 == 1) ret[n-1-i] = '#';
        x /= 2;
    }
    return ret;
}

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer(n);
    for(int i = 0; i < n; i++){
        answer[i] = i2str1(arr1[i] | arr2[i], n);
    }
    return answer;
}

i2str1 함수는 비트 연산을 이용해 정수로부터 문자열 배열을 만드는 함수입니다. 1을 i칸 밀어 AND를 취하면 x의 비트 기준 i번째 칸이 0인지 1인지 알 수 있습니다. 

 

i2str2 함수는 2로 나눈 나머지를 취하고 2로 나누는 작업을 반복해서 문자열 배열을 만드는 함수입니다. 가장 정석적인 방법입니다. 두 함수 모두 string ret의 초기값을 모두 공백으로 채워뒀기 때문에 i번째 칸이 0일 때에는 별도의 처리가 필요하지 않습니다.

 

solution 함수에서 answer[i]에 값을 넣을 때 i2str1 함수를 사용해도 되고 i2str2 함수를 사용해도 됩니다. 그냥 두 함수 모두를 보여드리고 싶어서 그랬습니다. 또 i2str1, i2str2를 굳이 함수로 빼지 않고 solution 내에서 써도 큰 상관은 없습니다.

 

코드(Python)

def i2str1(x, n):
    ret = ''
    for i in range(n-1, -1, -1):
        if x & (1 << i): ret += '#'
        else: ret += ' '
    return ret

def i2str2(x, n):
    ret = ''
    for i in range(n):
        if x % 2 == 1: ret += '#'
        else: ret += ' '
        x //= 2
    return ret[::-1]

def i2str3(x, n):
    s = bin(x)[2:].zfill(n)
    return s.replace('0',' ').replace('1','#')

def solution(n, arr1, arr2):
    answer = []
    for i in range(n):
        answer.append(i2str2(arr1[i] | arr2[i], n))
    return answer

    #return [i2str3(arr1[i] | arr2[i], n) for i in range(n)]

i2str1 함수는 비트 연산을 이용해 정수로부터 문자열 배열을 만드는 함수입니다. 1을 i칸 밀어 AND를 취하면 x의 비트 기준 i번째 칸이 0인지 1인지 알 수 있습니다. 제일 상위비트부터 정해져야 하므로 i는 n-1에서 0까지 돕니다.

 

i2str2 함수는 2로 나눈 나머지를 취하고 2로 나누는 작업을 반복해서 문자열 배열을 만드는 함수입니다. 가장 정석적인 방법입니다. for문을 돌고난 후에는 ret에 문자열이 거꾸로 있게 되므로 ret[::-1]을 통해 문자열을 뒤집어 반환해야 합니다.

 

i2str3 함수는 파이썬의 bin 함수를 이용한 방법입니다. bin 함수는 0b___ 형태로 값을 반환하기 때문에 slicing을 통해 0b를 제거했고 zfill을 통해 앞에 0을 추가해줬습니다. 이후 replace 메소드를 통해 0을 공백으로, 1을 #으로 바꾼 후 반환하면 됩니다.

 

solution 함수에서는 i2str1, i2str2, i2str3 중 어느 것을 이용해도 상관없습니다. 또한 주석처리한 구문과 같이 list comprehension을 이용해 solution 함수를 한 줄로 처리할수도 있긴 합니다. 너무 남발하면 코드가 알아보기 힘들게 되겠지만 코딩이 많이 익숙해진 후에는 틈틈히 시도해보시면 좋을 것 같습니다.

 

코드(JAVA)

class Solution {
    String i2str1(int x, int n) {
        String ret = "";
        for(int i = n-1; i >= 0; i--){
            if((x & (1 << i)) != 0) ret += "#";
            else ret += " ";
        }
        return ret;
    }
   
    String i2str2(int x, int n) {
        String tmp = "";
        for(int i = 0; i < n; i++){
            if(x % 2 == 1) tmp += "#";
            else tmp += " ";
            x /= 2;
        }
        String ret = ""; // String tmp를 reverse 시킴
        for(int i = 0; i < n; i++)
            ret += tmp.charAt(n-1-i);
        return ret;
    }
    
    String i2str3(int x, int n) {
        String ret = Integer.toBinaryString(x);
        while(ret.length() < n) ret = " " + ret;
        return ret.replace('0', ' ').replace('1', '#');
    }
    
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        for(int i = 0; i < n; i++)
            answer[i] = i2str3(arr1[i] | arr2[i], n);
        return answer;
    }
}

i2str1 함수는 비트 연산을 이용해 정수로부터 문자열 배열을 만드는 함수입니다. 1을 i칸 밀어 AND를 취하면 x의 비트 기준 i번째 칸이 0인지 1인지 알 수 있습니다. 제일 상위비트부터 정해져야 하므로 i는 n-1에서 0까지 돕니다.

 

i2str2 함수는 2로 나눈 나머지를 취하고 2로 나누는 작업을 반복해서 문자열 배열을 만드는 함수입니다. 가장 정석적인 방법입니다. for문을 돌고난 후에는 tmp에 문자열이 거꾸로 있게 되므로 for문을 돌면서 문자열을 뒤집은 결과를 ret에 저장해 반환해야 합니다.

 

i2str3 함수는 자바의 bin 함수를 이용한 방법입니다. 길이를 맞춰주기 위해 while문을 이용해서 앞에 0을 추가해줬습니다. 이후 replace 메소드를 통해 0을 공백으로, 1을 #으로 바꾼 후 반환하면 됩니다.