- LCs
- ํ๋ก๊ทธ๋๋จธ์ค
- ๋ฐฑ์๋ ํ๋ฆฌ์จ๋ณด๋ฉ
- ์๊ณ ๋ฆฌ์ฆ
- DP
- ๊ฐ์ฅ๊ฐ๊น์ด๊ณตํต์กฐ์
- Union-Find
- ์ด๋ถํ์
- DFS
- nestjs
- ์นด์นด์ค2021
- ํธ๋ฆฌ
- ๋นํธ๋งต
- go
- ํ๋ฆฌ์จ๋ณด๋ฉ
- js
- golang
- ์์ฝ๋
- ์นด์นด์ค ์ฝํ
- ์ํฐ๋
- ๋นํธ๋ง์คํน
- ์น๋ฆฐ์ด
- ์ฌ๋ผ์ด๋ฉ ์๋์ฐ
- BFS
- ๋์ ํ๋ก๊ทธ๋๋ฐ
- ๋ค์ต์คํธ๋ผ
- Python
- C++
- ์ฌ๊ท
- ๋ฐฑ์ค
- Today
- Total
Hello Ocean! ๐ผ
[C++/ํ๋ก๊ทธ๋๋จธ์ค] ๋ถ๋ ์ฌ์ฉ์ ๋ณธ๋ฌธ
๋ฌธ์
https://programmers.co.kr/learn/courses/30/lessons/64064
์ด๋ฒคํธ ์๋ชจ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด user_id์
๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด banned_id๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋,
๋น์ฒจ์์ ์ ์ธ๋์ด์ผ ํ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ช๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ๊ฐ๋ฅํ ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
[์ ํ์ฌํญ]
- user_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 8 ์ดํ์ ๋๋ค.
- user_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ค์ ์๋ก ์ค๋ณต๋์ง ์์ต๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์๋ก๋ง์ผ๋ก ๊ตฌ์ฑ๋์ด ์์ต๋๋ค.
- banned_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ user_id ๋ฐฐ์ด์ ํฌ๊ธฐ ์ดํ์ ๋๋ค.
- banned_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์, ๊ฐ๋ฆฌ๊ธฐ ์ํ ๋ฌธ์ '*' ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ '*' ๋ฌธ์๋ฅผ ํ๋ ์ด์ ํฌํจํ๊ณ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ํ๋๋ ์๋ชจ์ ์์ด๋ ์ค ํ๋์ ํด๋นํ๊ณ ๊ฐ์ ์๋ชจ์ ์์ด๋๊ฐ ์ค๋ณตํด์ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ๋ ์์ต๋๋ค.
- ์ ์ฌ ์์ด๋ ๋ชฉ๋ก๋ค์ ๊ตฌํ์ ๋ ์์ด๋๋ค์ด ๋์ด๋ ์์์ ๊ด๊ณ์์ด ์์ด๋ ๋ชฉ๋ก์ ๋ด์ฉ์ด ๋์ผํ๋ค๋ฉด ๊ฐ์ ๊ฒ์ผ๋ก ์ฒ๋ฆฌํ์ฌ ํ๋๋ก ์ธ๋ฉด ๋ฉ๋๋ค.
ํ์ด
[์ฌ๊ทํจ์ ์ด์ฉ]
user_id๋ฐฐ์ด์ ๊ธธ์ด๊ฐ ์ต๋ 8์ด๊ธฐ ๋๋ฌธ์, ์๊ฐ๋ณต์ก๋ ๋ฉด์์ ์ถฉ๋ถํ ์ฌ์ ๊ฐ ์์๋ค.
๊ทธ๋์ ์ฌ๊ทํจ์๋ก ๊ตฌํํ๋ค.
์ฌ๊ทํจ์์ ์ธ์๋ก banned_id ๋ฐฐ์ด์ ๋ํ idx, bitmap(์ง๊ธ๊น์ง ๋ฝ์ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก)์ ์ฃผ์๋ค.
[์ ๊ท์]
banned_id๋ค์ ์ ๊ท์ํํ๋ก ๋ง๋ค๊ธฐ ์ํด ์์ ^, ๋ค์ $๋ฅผ ์ถ๊ฐํ๊ณ , *๋ฅผ .์ผ๋ก ๋ฐ๊ฟ์ฃผ์๋ค.
[๋นํธ๋งต]
๋ฝ์ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ํ๋ด๊ธฐ ์ํด ๋นํธ๋งต์ ์ฌ์ฉํ๋ค.
0, 2๋ฒ์งธ ์์ด๋๊ฐ ๋ฝํ์ผ๋ฉด -> 00000101(2)
์ฒ์์๋, bool๋ฐฐ์ด์ ์ด์ฉํด์ ์ ์ฌ ์์ด๋์์ ์ค๋ณต์ผ๋ก ๋ค์ด๊ฐ์ง ์๋๋ก ํ์ธํด์ฃผ์๋ค.
๊ทธ๋ฐ๋ฐ,
user_id | banned_id |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["*rodo", "*rodo", "******"] |
์์ ํ ์คํธ ์ผ์ด์ค์์
frodo, crodo, frodoc
crodo, frodo, frodoc ๊ฐ ์ค๋ณต์ผ๋ก ์ธ์ด์ง๋ ๋ฌธ์ ๊ฐ ์์๋ค ใ ใ
banned_id์ ๊ฐ์ ๋ฌธ์์ด์ด ๋๊ฐ๊ฐ ์์๊ธฐ ๋๋ฌธ์ด๋ค.
์ด ์ ์ ํด๊ฒฐํ๊ธฐ ์ํด, count๋ฅผ ์ธ๋ ๋ฐฉ์์์, set์ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ชจ๋ ๋ฃ๊ณ
๋ง์ง๋ง์ set์ ํฌ๊ธฐ๋ฅผ returnํ๋ ๋ฐฉ์์ ์ฌ์ฉํ๊ณ ์ ํ๋ค.
๊ทธ๋์ bool vector๋ฅผ set์ ๋ฃ๋ ๊ฒ ๋ณด๋ค๋ bitmap์ด ํจ์จ์ ์ผ ๊ฒ ๊ฐ์ bitmap์ ์ด์ฉํ๋ ๋ฐฉ์์ผ๋ก ๋ณ๊ฒฝํ์๋ค.
์ฝ๋
์ ์ฒด ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค!
#include <string>
#include <vector>
#include <regex>
#include <algorithm>
#include <unordered_set>
using namespace std;
vector<string> user_ids;
vector<string> banned_ids;
unordered_set<int> bitmaps;
void recursive(int idx, int bitmap) {
regex re(banned_ids[idx]);
for (int i=0;i<user_ids.size();i++) {
if (bitmap & (1<<i)) continue;
if (regex_match(user_ids[i], re)) {
bitmap += (1<<i);
if (idx == banned_ids.size()-1) {
bitmaps.insert(bitmap);
continue;
}
recursive(idx+1, bitmap);
bitmap -= (1<<i);
}
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
user_ids = user_id; banned_ids = banned_id; // ์ ์ญ๋ณ์๋ก ๋ง๋ค๊ธฐ
// ์ ๊ท์ํํ๋ก ๋ง๋ค๊ธฐ (^๋ฌธ์์ด.$)
for (int i=0;i<banned_ids.size();i++) {
banned_ids[i].insert(0,"^");
replace(banned_ids[i].begin(), banned_ids[i].end(), '*', '.');
banned_ids[i] += "$";
}
recursive(0,0);
int answer = bitmaps.size();
return answer;
}
๊ฒฐ๊ณผ
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/ํ๋ก๊ทธ๋๋จธ์ค] ๋จ์ด ๋ณํ (0) | 2022.01.12 |
---|---|
[C++/ํ๋ก๊ทธ๋๋จธ์ค] ๋ณด์ ์ผํ (2020 ์นด์นด์ค ์ธํด์ญ) (0) | 2021.12.30 |
[ํ๋ก๊ทธ๋๋จธ์ค/C++] ํ ํธ์ง (3) | 2021.12.08 |
[ํ๋ก๊ทธ๋๋จธ์ค/C++] [1์ฐจ] ์ ํ๋ฒ์ค (0) | 2021.12.08 |
[C++/ํ๋ก๊ทธ๋๋จธ์ค] ์ถ์ ํธ๋ํฝ (0) | 2021.11.17 |