https://programmers.co.kr/learn/courses/30/lessons/17681
코딩테스트 연습 - [1차] 비밀지도 | 프로그래머스
비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1
programmers.co.kr
이 문제는 비트 마스크를 이용해서 쉽게 풀 수 있다.
전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
라는 문제의 조건에서 두 지도를 OR 연산한 결과가 전체 지도라는 것을 알 수 있다.
지도 1과 지도 2의 각 행을 OR연산한 후에 1이 있는 곳에는 '#' (벽)을, 0이 있는 곳에는 ' ' (공백)을 문자열에 추가하여 answer벡터에 넣어준다. 1이 있는 곳은 shift연산을 통해서 알아낼 수 있다.
예를 들어 첫 번째 예제에 나와있는 전체 지도의 3번째 줄은 11101이 되는데
(1<<j) (0<=j, j < n)한 값과 (지도 1과 2의 OR 연산한 결과)를 AND 연산해줬을 때, 0이 아닌 값이 나오면 1이 있다는 뜻이다.
이 예제의 경우
11101 & 10000 = 10000 (0이 아니므로 벽#)
11101 & 01000 = 01000 (0이 아니므로 벽#)
11101 & 00100 = 00100 (0이 아니므로 벽#)
11101 & 00010 = 00000 (0이므로 공백)
11101 & 00001 = 00001 (0이 아니므로 벽#)
위와 같은 결과가 나와서 문자열은 "### #" 이 된다.
이런 식으로 모든 행에 대해서 전체 지도를 구해줄 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#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++) {
int tmp = (arr1[i] | arr2[i]);
string s = "";
for(int j=n-1; j>=0; j--) {
if(tmp & (1<<j)) {
s += "#";
} else {
s += " ";
}
}
answer.push_back(s);
}
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 프렌즈4블록 c++ (0) | 2019.08.29 |
|---|---|
| 프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 다트 게임 c++ (0) | 2019.08.28 |
| 프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 실패율 c++ (0) | 2019.08.22 |
| 프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0) | 2019.08.22 |
| 프로그래머스 탑 (c++) (0) | 2019.08.20 |