[프로그래머스] Lv.1 비밀지도 c++

https://school.programmers.co.kr/learn/courses/30/lessons/17681

프로그래머스

 

2018 KAKAO BLIND RECRUITMENT에 나온 문제이다. 

암호화된 두 개의 비밀지도를 조합하여 길을 표시하려고 한다.

조건

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

풀이 방법

나는 크게 두가지 방법으로 풀었다.

1. #inlcude<bitset>헤더파일 사용

2. 2로 직접 나누어 나머지를 구해 이진수 구하기 (근본 방법)

 

물론 1번 방법이 코드도 훨씬 간결하고 편하다. 숫자만 넣으면 자동으로 이진수로 변환해 준다...!

하지만 원리를 알면 더 이해하기 쉬우므로 2진수 변환도 직접 해보는 걸 추천한다!

 

2진수 변환 과정을 간단히 말하면 아래와 같다.

20을 변환할 경우:

1. 20/2 = 10, 20%2 = 0
2. 10/2 = 5, 10%2 = 0
3. 5/2 = 2, 5%2 = 1
4. 2/2 = 1, 2%2 = 0 (2로 나누었을 때 몫이 0이거나 1일 경우 종료)

20을 이진수 변환 시 10100이 나온다.

만약 지도 크기가 5인데 이진수 변환시 값이 1001처럼 4 자릿수가 나온다면 맨 앞에 부족한 길이만큼 0을 추가해 주면 된다. (01001) 

 

아래는 bitset의 간단한 예시코드다.

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    int num = 20; // 변환할 숫자
    bitset<8> binary(num); // 8비트(bit)로 변환

    cout << "Number: " << num << endl;
    cout << "Binary: " << binary << endl;

    return 0;
}
// Number: 20
// Binary: 00010100

 

풀이 코드 1 (#include<bitset>)

#include <string>
#include <iostream>
#include <vector>
#include <bitset>

#define MAX_SIZE 16
using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    string s1 ="", s2="";
    for(int i=0; i<n; i++){
        string tmp = "";
        bitset<MAX_SIZE> bit1(arr1[i]);
        bitset<MAX_SIZE> bit2(arr2[i]);
        
        s1 = bit1.to_string();
        s2 = bit2.to_string();
        
        for(int i=MAX_SIZE-n; i<MAX_SIZE; i++){
            if(s1[i] == '1' || s2[i] == '1') tmp+="#";
            else tmp+=" ";
        }
        answer.push_back(tmp);
    }
    return answer;
}

 

풀이 코드 2

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string s1 ="", s2="";
string intToBinary(int bit, int n);
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for(int i=0; i<n; i++){
        string tmp = "";
        s1 = intToBinary(arr1[i], n);
        s2 = intToBinary(arr2[i], n);
        
        for(int i=0; i<n; i++){
            if(s1[i] == '1' || s2[i] == '1') tmp+="#";
            else tmp+=" ";
        }
        answer.push_back(tmp);
    }
    return answer;
}

string intToBinary(int bit, int n){
    string bin ="";
    while(1){
        if(bit == 1 || bit == 0){
            bin+=to_string(bit);
            break;
        }
        bin+=to_string(bit%2);
        bit/=2;
    }
    while(bin.size() != n) bin+="0";
    reverse(bin.begin(), bin.end());
    return bin;
}

 

 

 

 

 

지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다.