๐ฃ ๋ฌธ์ ์ดํด
์ด๋ฒคํธ ์๋ชจ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด user_id์
๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด banned_id๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋,
๋น์ฒจ์์ ์ ์ธ๋์ด์ผ ํ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ช ๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ๊ฐ๋ฅํ ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ผ ํ๋ค.
๐ญ ํ์ด ๊ณผ์
๋จผ์ banned_id ์ ๊ธธ์ด๊ฐ ๋์ผํ user_id ๋ฅผ ์ฐพ๊ณ ,
* ๋ฌธ์๋ฅผ ์ ์ธํ ๋ชจ๋ ๋ฌธ์๊ฐ ๋์ผํ๋ค๋ฉด ๊ฐ์ ์์ด๋๋ผ๊ณ ๊ฐ์ ํ๊ณ , ๊ทธ ์์ด๋์ ์ธ๋ฑ์ค๋ฅผ ์ ์ฅํ๋ค.
๊ฐ banned_id ๋ณ๋ก ๊ฐ๋ฅํ user_id ํ๋ณด๊ฐ ํ ๊ฐ ์ด์์ด๋ฏ๋ก, ๋ชจ๋ ์กฐํฉ์ ์๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๋ค.
๋์ผํ ์กฐํฉ์ ์ค๋ณต์ด ๊ฐ๋ฅํ๋ค๋ฉด ๊ณฑํ๋ฉด ๋์ง๋ง, ์ค๋ณต์ ํ๋ฝํ์ง ์์ผ๋ฏ๋ก ์ฒดํฌํด์ค์ผ ํ๋ค.
๋ฐฉ๋ฒ์ ๊ณ ๋ฏผํ๋ค, ๋ค๋ฅธ ํ์ด๋ฅผ ์ฐพ์๋ณด๋ฉฐ ๋นํธ๋ง์คํฌ ๋ฐฉ์์ผ๋ก ์ค๋ณต์ ์ ์ธํ ๊ฐ์ง์๋ฅผ ์ฒดํฌํ๋ค.
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <vector>
using namespace std;
bool isVisited[1 << 8];
void bitMask(int index, int bnArrSize, int bitmask, vector<vector<int>> &vec) {
if (index == bnArrSize) {
isVisited[bitmask] = true;
return;
}
for (auto num:vec[index]) {
if (bitmask & (1 << num)) continue; // ์ด๋ฏธ ํ์ํ ์์ด๋์ธ ๊ฒฝ์ฐ ํจ์ค
bitMask(index + 1, bnArrSize, bitmask | (1 << num), vec);
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
vector<vector<int>> eq_Index(banned_id.size());
int answer = 0, check = 1;
/*************************** ๋ถ๋ ์์ด๋๋ณ๋ก ์ผ์นํ๋ ์์ด๋ ์ธ๋ฑ์ค ์ ์ฅ ***************************/
for (int i = 0; i < banned_id.size(); ++i) {
int bidLength = banned_id[i].length(); // ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๊ธธ์ด
for (int j = 0; j < user_id.size(); ++j) {
int uidLength = user_id[j].length(); // ์ฌ์ฉ์ ์์ด๋ ๊ธธ์ด
check = 1;
if (uidLength != bidLength) { // ์์ด๋ ๊ธธ์ด๊ฐ ๊ฐ์ง ์์ผ๋ฉด ํจ์ค
check = -1;
continue;
}else { // ์์ด๋ ๊ธธ์ด๊ฐ ๊ฐ๋ค๋ฉด ๋ฌธ์ ๋น๊ต
for (int k = 0; k < bidLength; ++k) {
if (banned_id[i][k] == '*') { // *๋ฌธ์๋ ๋น๊ต ํจ์ค
continue;
}else {
if (banned_id[i][k] != user_id[j][k]) { // ๋ฌธ์๊ฐ ๋ค๋ฅด๋ค๋ฉด check๋ฅผ -1๋ก ํ๊ณ ๋ฌธ์ ๋น๊ต ์ข
๋ฃ
check = -1;
break;
}
}
}
}
if (check == 1) { // ๋ ์์ด๋๊ฐ ๊ฐ๋ค๊ณ ํ๋จํ ๊ฒฝ์ฐ
cout << "banned_id: " << banned_id[i] << "user_id: " << user_id[j] << '\n';
eq_Index[i].push_back(j);
}
}
}
/*************************** ๋นํธ๋ง์คํฌ๋ก ์กด์ฌํ๋ ํ๋ณด๊ตฐ ์กฐ์ฌ ***************************/
bitMask(0, banned_id.size(), 0, eq_Index);
for (bool temp:isVisited) {
if (temp == true) answer++;
}
return answer;
}
๐ ๋ฐฐ์ด ์
๋นํธ๋ง์คํฌ๋ฅผ ์ฌ์ฉํ๋ฉฐ ์ฝ๋๋ ๊ฐ๊ฒฐํ๊ณ , ์งง์ ์ํ์๊ฐ์ผ๋ก ์ฐ์ฐํ ์ ์๋ค๋ ์ฅ์ ์ ๊ฒฝํํ๋ค.
์ด์ ์ ์ฑ (์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต)์ผ๋ก ๋นํธ๋ง์คํฌ๋ฅผ ์ ํ ์ ์ด ์๋๋ฐ,
์ค์ ๋ฌธ์ ๋ก ํ์ดํ๋ฉฐ ์ดํดํ๊ณ ๋ค์ ์ด๋ก ์ ๋ค์ ์ฌ๋ณด๋ ํจ์ฌ ์ดํด๊ฐ ์๋๋ค.
์ญ์ ๋ฌธ์ ํ์ด ๋ค๋ค์ต์ ์ธ๋ฏ๐
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 1918 ํ์ ํ๊ธฐ์ / ์คํ(Stack) (0) | 2020.07.18 |
---|---|
[BOJ] ๋ฐฑ์ค 10828 ์คํ / ์คํ(Stack) (0) | 2020.07.17 |
[2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ] ํํ (0) | 2020.05.01 |
[2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ] ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์ (0) | 2020.05.01 |
[BOJ] ๋ฐฑ์ค 11055 ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ ์์ด / ๋์ ๊ณํ๋ฒ(Dynamic-Programming) (0) | 2020.04.27 |