본문 바로가기
알고리즘

[프로그래머스] 알고리즘 78일차 : 비밀지도

by SiO2whocode 2021. 2. 3.
반응형

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

 

코딩테스트 연습 - [1차] 비밀지도

비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다

programmers.co.kr

C++ 2018 카카오 블라인드 리크루팅

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

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

접근방법

N*N배열을 만들어서 십진수를 이진수로 변환한 값을 저장하고 그렇게 저장한 두 배열을 하나하나 or연산을 하여

결과를 n*n의 bool 배열에 저장한다. bool배열을 전체탐색하면서 answer에 "#" 혹은 " "을 저장한다.

였는데 이 코드도 물론 통과된다. 하지만 쓰면서 이렇게 반복문을 많이 쓴적이 있나 싶을 정도로 대책없이 써댔다. 

백준에서는 데이터 사이즈가 너무 커서 반복문을 특히 이중반복문을 여러개 쓰면 반드시 시간초과가 났는데

여기서는 저렇게 써도 잘 통과되긴 했다.

 

*

하지만 다른 사람의 풀이를 보고 내 40줄코드가 한없이 지저분해 보여서 고쳐봤다.

비트연산자를 잘 활용하면 반복문을 많이 쓸 필요가 없는 문제이다.

풀이 시간 ( 고쳐서 푼 것 까지 30분 ) 

 

소스코드1(원래풀이)

#include <string>
#include <vector>
using namespace std;
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    int map1[n][n];
    int map2[n][n];
    for(int i = 0 ; i < n ; i++){
        int dec = arr1[i];
        for(int j = n-1 ; j >= 0 ; j--){
            map1[i][j] = dec%2;
            dec /= 2;
        }
    }
    for(int i = 0 ; i < n ; i++){
        int dec = arr2[i];
        for(int j = n-1 ; j >= 0 ; j--){
            map2[i][j] = dec%2;
            dec /= 2;
        }
    }
    
    bool final[n][n];
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            final[i][j] = map1[i][j] || map2[i][j];
        }
    }
    
    for(int i = 0 ; i < n ; i++){
        string row = "";
        for(int j = 0 ; j < n ; j++){
            row += final[i][j] ? "#" : " ";            
        }
        answer.push_back(row);
    }
    return answer;
}

이런 코드가

#include <string>
#include <vector>
using namespace std;
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for(int i = 0 ; i < n ; i++){
        arr1[i] = arr1[i]|arr2[i];
        string row = "";
        for(int j = 0 ; j < n ; j++){
            row = (arr1[i] % 2 == 0 ? " " : "#")+ row;
            arr1[i] = arr1[i] >> 1;
        }
        answer.push_back(row);
    }
    
    return answer;
}

이걸로 끝난다. ㄷㄷ

십진수에 | 연산자를 쓰면 이진수 비트연산이 수행된 값이 저장된다. (10진수로)

기존 풀이에서 맨 앞에 이중for문 세개를 저 연산자가 해결해버림

10진수를 2진수로 치환해서 저장하는 과정은 순서가 거꾸로 들어가야해서 + row 식으로 써줘야한다.

그리고 나누기 대신 >> 1 비트연산쓰는 것도.

👍👍

반응형

댓글0