[프로그래머스/C++] [1차]비밀지도 (Lv.1)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/17681?language=cpp

프로그래머스

 

1. 문제 접근

이 문제는 두 개의 지도를 합쳐서 하나의 비밀지도를 만드는 문제이다. 각 지도는 숫자 배열로 주어지는데, 이 숫자는 실제로는 이진수 형태의 지도 한 줄을 의미한다.

예를 들어 n = 5일 때 숫자 14는 이진수로 바꾸면 다음과 같다.

14 = 01110

여기서
1 = 벽
0 = 공백
으로 보면 된다.

 

 

따라서 최종 지도는 다음 규칙으로 만들어진다.( 즉, 두 지도 중 하나라도 벽이면 최종 결과도 벽이다. )

arr1 결과	arr2 결과	결과
0	0	공백
1	0	벽
0	1	벽
1	1	벽

 

이 규칙은 비트 연산 중 OR 연산과 동일하다.

arr1[i] | arr2[i]

//따라서 핵심 접근은 아래와 같다.
1. arr1[i]와 arr2[i]를 OR 연산한다.
2. OR 연산 결과를 이진수 문자열로 바꾼다.
3. 이진수 길이가 n보다 짧으면 0을 채운다.
4. 1은 '#', 0은 ' '으로 바꾼다.

 

---

2. 풀이

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

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {

    vector<string> v;
    vector<string> answer;

    for(int i = 0; i < n; i++){

        // 두 지도 중 하나라도 벽이면 벽이므로 OR 연산 사용
        int a = arr1[i] | arr2[i];
        string s;

        // 10진수를 2진수 문자열로 변환
        // 단, 나머지를 붙이는 방식이라 거꾸로 저장됨
        while(a != 0){
            s += to_string(a % 2);
            a = a / 2;
        }

        // 지도 한 줄의 길이는 반드시 n이어야 하므로 부족한 만큼 0 채우기
        // 현재 문자열은 뒤집기 전이므로 뒤에 0을 붙이면 나중에 앞자리 0이 됨
        while(s.size() < n){
            s += "0";
        }

        // 거꾸로 저장된 2진수 문자열을 정상 순서로 뒤집기
        reverse(s.begin(), s.end());

        // 변환된 2진수 문자열 저장
        v.push_back(s);
    }

    // 2진수 문자열을 지도 문자열로 변환
    for(int i = 0; i < n; i++){
        string s2 = "";

        for(int j = 0; j < n; j++){
            if(v[i][j] == '1') {
                s2 += '#';
            }
            else {
                s2 += ' ';
            }
        }

        answer.push_back(s2);
    }

    return answer;
}

 

---

3. 문법

• 비트 OR 연산자 | 
  

  int a = arr1[i] | arr2[i];

  • |는 비트 단위 OR 연산자이다.
  • 두 비트 중 하나라도 1이면 결과가 1이 된다.
  • 예를 들어 다음과 같다.
    

    arr1 = 01001
    arr2 = 11110
    결과 = 11111

    이 문제에서 1은 벽을 의미한다.
    => 따라서 두 지도 중 하나라도 벽이면 최종 지도도 벽이 되어야 하므로 OR 연산을 사용하면 된다
  
  
  
• 10진수를 2진수로 변환하기
  (참고) [프로그래머스/C++] 삼진법 뒤집기 (Lv.1)
  

  while(a != 0){
      s += to_string(a % 2);
      a = a / 2;
  }

   
  • 10진수를 2진수로 바꿀 때는 숫자를 계속 2로 나누면서 나머지를 저장하면 된다.
  • 예를 들어 14 를 이진수로 바꾸면 다음과 같다.
    

    14 / 2 = 7 ... 0
    7  / 2 = 3 ... 1
    3  / 2 = 1 ... 1
    1  / 2 = 0 ... 1
    
    //나머지를 순서대로 저장하면
    0111
    
    //그런데 실제 이진수는 
    1110
    즉, 나머지를 바로 문자열에 붙이면 s += to_string(a % 2); 거꾸로 저장되는 구조

• 부족한 0 채우기 
  이 문제에서 지도 한 줄의 길이는 반드시 n이어야 한다.
  예를 들어 n = 5인데 숫자 14 를 이진수로 바꾸면
  

  1110 이다
  
  하지만 지도 한 줄은 길이가 5이어야 하므로 실제로는
  
  01110 이다.

  
  여기서 중요한 점은 현재 코드에서는 이진수를 거꾸로 저장하고 있다는 것이다.
  

  while(a != 0){
      s += to_string(a % 2);
      a = a / 2;
  }
  
  //예를 들어 14 를 처리하면 s에는 다음처럼 저장된다.
  s = "0111"
  
  //이 상태에서 부족한 0을 뒤에 붙인다.
  while(s.size() < n){
      s += "0";
  }
  
  //결과는
  s = "01110"
  
  //이후 reverse()를 하면
  s = "01110"
  
  //즉 여기서 생각할 핵심은
  - 뒤집기 전에 0을 뒤에 붙이면,
  - 뒤집은 후에는 앞자리 0이 된다. why? reverse 해야하니

---

4. 최종 요약

이 문제의 핵심은 크게 두 가지이다.

• 첫 번째, OR 연산으로 두 지도를 합치기 두 지도 중 하나라도 벽이면 최종 결과도 벽이다.
  => 따라서 비트 OR 연산을 사용한다.
  

  int a = arr1[i] | arr2[i];

• 두 번째, 이진수 길이를 n으로 맞추기
  10진수를 2진수로 바꾸면 앞자리 0이 생략될 수 있다. 하지만 문제에서는 지도 한 줄의 길이가 반드시 n이어야 한다.
  ⇒ 따라서 부족한 만큼 0을 채워야 한다.
  
  이 풀이에서는 나머지를 이용해 이진수를 만들기 때문에 문자열이 거꾸로 저장된다.
  그래서 중요한 순서는 다음과 같다.
  

  1. 10진수를 2진수 문자열로 변환한다.
  2. 부족한 0을 뒤에 붙인다. // 이 아이디어 기억!! 
  3. reverse로 뒤집는다.
  4. 1은 '#', 0은 ' '으로 변환한다.

이 문제는 단순 문자열 문제처럼 보이지만, 실제 핵심은 비트 OR 연산과 이진수 변환 방식을 이해하는 것이다.