Lv1_[[1차] 비밀지도, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

두 가지의 풀이 방식을 설명

1. 10진수를 2진수로 변경하면서 0을 공백(" "), 1을 벽("#")으로 변환
2. bitset, regex_replace를 이용한 방법

 

1의 알고리즘

1. 두 장의 지도를 겹친다 → 동일 위치 숫자를 |(비트 OR 연산자)를 해준다.
2. 반복문을 통해 10진수를 2진수로 변환(2진수로 전부 변환 되고 n번 모두 수행할 때까지)
   1. 0을 공백(" "_), 1을 벽("#")으로 변환
   2. 변환된 string을 앞으로 붙이면서 누적 (2진수 변환 시 뒷자리부터 나오기 때문)
3. 변환 완료된 string answer에 저장

 

2의 알고리즘

1. 두 장의 지도를 겹친다 → 동일 위치 숫자를 |(비트 OR 연산자)를 해준다.
2. bitset에 숫자를 넣어서 2진수로 변경해준다. 선언시 16(최대값)으로 해야함(bitset<16>)
3. regex_replace로 "1"→"#", "0"→" "으로 변경
4. 변환 완료된 string을 begin()-(16-n) ~ end()까지 answer에 반환

 

#include <string>
#include <vector>
#include <bitset>
#include <regex>
 
#define MAX 16
 
using namespace std;
 
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    
    for(int i = 0; i < arr1.size(); i++)
    {
#if 1   // 10진수를 2진수로 변경하면서 0을 공백(" "), 1을 벽("#")으로 변환
        string str_map = "";
        int count = n;
        int num = arr1[i] | arr2[i];
        while((num > 0) || (count > 0))
        {
            int divide = num % 2;
            num = num / 2;
            
            string add_chr;
            (divide == 1) ? add_chr = "#" : add_chr = " ";
            str_map = add_chr + str_map;
            
            count--;
        }
        answer.push_back(str_map);
        
#else   // bitset, regex_replace를 이용한 방법
        int num = arr1[i] | arr2[i];
 
        bitset<MAX> bit = num;
        string str_bit = bit.to_string();
        cout << "str_bit : " << str_bit << endl;
        str_bit = regex_replace(str_bit, regex("1"), "#");
        str_bit = regex_replace(str_bit, regex("0"), " ");
        
        answer.emplace_back(string(str_bit.cbegin()+(MAX-n), str_bit.cend()));   
#endif
    }
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓